排序数组中查找上限的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的数组中不存在值，因此19的上限不存在，所以输出为：9的上限在数组中不存在。

输入

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

输出

3

说明：众所周知，x的上限是大于或等于x的最小值，这里x为2，数组中不存在2，数组中仅大于2的元素为3。所以输出为3。

方法

我们将讨论两种方法。让我们在下面的部分中看到它们：

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

这种方法的思路是，我们将通过简单地从数组的开头遍历到所需的元素或数组的末尾，找到给定排序数组中等于或大于给定数字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))，因为我们使用了额外的空间。

结论

在本教程中，我们实现了一个JavaScript程序，用于为给定的排序数组查找给定数字的上限。给定数字的上限是查找存在于给定数组中且等于给定数字的数字，如果不存在，则查找大于给定数字的数字。如果给定数组中没有一个元素大于给定数字，则它不存在。我们已经实现了线性搜索和二分搜索算法。