JavaScript 计算有序数组的上界

数组是一种线性数据结构，它包含对象，并且有序数组元素按升序排列。我们给定了一个有序数组和一个整数x。我们需要打印出从给定数组中整数x的上界。有序数组中值为x的上界是大于或等于x的最小元素，而下界是小于或等于x的最大成员。如果x的上界在数组中不存在，我们需要打印“x的上界在数组中不存在。

假设我们给定了一个有序数组和一个整数x为例

输入

Array = [1, 3, 5, 7, 9]
X = 19

输出

The ceiling of 19 does not exist in the array

说明

19或大于19个，数组中存在0值，这就是为什么19的上限不存在，所以输出结果是9的上限不存在于数组中。

输入

Array: [1, 3, 5, 7, 9]
X = 2

输出

解释：我们知道x的上限是大于或等于x的最小数，所以这里x是2，在数组中没有2，只有一个比2大的元素是3。所以输出是3。

方法

这里我们将讨论两种方法。让我们看看下面的部分。

方法1：通过线性搜索在排序数组中查找上限

这种方法的思想是，通过从数组的起始位置遍历到所需位置或数组的末尾，找到与给定数字x相等或大于x的元素。

示例

// function to implement the linear search 
function findCeiling(arr, x){   
   var len = arr.length // getting length of the array 

   // traversing over the given array 
   for(var i =0; i<len; i++){

      // if the current number is equal to current number 
      // or greater than the given number, return it
      if(x <= arr[i]){
         return i;
      }
   }

   // as we have travesed over the array 
   // no element is smaller as compare to the given element     
   return -1;
}

// defining the array 
var arr = [1, 2, 4, 5, 8, 19, 25]
var num = 15
console.log("The given array is: ");
console.log(arr);

// calling the function 
var idx = findCeiling(arr,num);
if(idx == -1){
   console.log("Ceiling of given number " + num + " does not exists");
}
else{
   console.log("Ceiling of given number " + num + " in the array is " + arr[idx]);
}
num = 78
idx = findCeiling(arr,num);
if(idx == -1){
   console.log("Ceiling of the given number " + num + " does not exists");
}
else{
   console.log("Ceiling of the given number " + num + " in the array is " + arr[idx]);
}

时间复杂度：O(N)，其中N是数组的大小。

空间复杂度：O(1)，因为我们没有使用任何额外的空间。

方法2：通过二分查找找到排序数组中的上界

这种方法的思想是我们将遍历数组的范围缩小，而不是遍历整个数组。因为我们知道数组是有序的，所以我们可以使用二分查找将数组分成两部分，并检查

示例

// function to implement the linear search 
function findCeiling(arr, l, h, x){

   // defining the end cases 
   if(x <= arr[l]){
      return l;
   }
   else if(x > arr[h]){
      return -1;
   }    
   var mid = (l + h)/2;   

   // if current element and x are same, return current index  
   if(arr[mid] == x){
      return mid;
   }
   else if(arr[mid] < x){        
      if(mid + 1 <= h && x <= arr[mid + 1]){
         return mid +1;
      }
      else{
         return findCeiling(arr, mid+1, h, x);
      }
   }
   else{
      if(mid - 1 >= l && x > arr[mid - 1]){
         return mid;
      }
      else{
         return findCeiling(arr,l, mid-1, x);
      }
   }
}

// defining the array 
var arr = [1, 2, 4, 5, 8, 19, 25]
var num = 15
console.log("The given array is: ");
console.log(arr);

// calling the function 
var idx = findCeiling(arr,0, arr.length-1, num);
if(idx == -1){
   console.log("Ceiling of given number " + num + " does not exists");
}
else{
   console.log("Ceiling of given number " + num + " in the array is " + arr[idx]);
}
num = 78
idx = findCeiling(arr, 0, arr.length-1, num);
if(idx == -1){
   console.log("Ceiling of the given number " + num + " does not exists");
}
else{
   console.log("Ceiling of the given number " + num + " in the array is " + arr[idx]);
}

时间复杂度: O(log(N))，其中N是数组的大小。

空间复杂度: O(log(N))，因为我们使用了额外的空间。