在排序数组中寻找上界的JavaScript程序

数组是一种线性数据结构，包含对象，并且在排序数组中，元素按增加的顺序存储。我们已经有了一个排序数组和一个整数x。我们要从给定的数组中打印整数x的上界。排序数组中x的上界是大于或等于x的最小元素，而下界是小于或等于x的最大成员。如果x的上界不存在于数组中，我们必须打印“x的上界不存在于数组中。”

假设我们有一个排序数组和一个整数x，如下所示：

输入

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

输出

19的上界不存在于数组中

说明

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 findCeiling(arr, x){   
   var len = arr.length // 获取数组的长度 

   // 遍历给定的数组
   for(var i =0; i<len; i++){

      // 如果当前数字等于当前数字或大于给定数字，则返回它
      if(x <= arr[i]){
         return i;
      }
   }

   // 由于我们已经遍历了整个数组，因此没有元素比给定元素小
   return -1;
}

// 定义数组
var arr = [1, 2, 4, 5, 8, 19, 25]
var num = 15
console.log("给定的数组是：");
console.log(arr);

// 调用函数
var idx = findCeiling(arr,num);
if(idx == -1){
   console.log("给定数字 " + num + " 的上界不存在");
}
else{
   console.log("给定数字 " + num + " 在数组中的上界是 " + arr[idx]);
}
num = 78
idx = findCeiling(arr,num);
if(idx == -1){
   console.log("给定数字 " + num + " 的上界不存在");
}
else{
   console.log("给定数字 " + num + " 在数组中的上界是 " + arr[idx]);
}

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

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

解法 2：通过二分搜索在排序数组中找到上界

这种方法的想法是我们要遍历数组但不是整个数组。因为我们知道我们有一个排序数组，所以在这里我们应用二分搜索，将数组从中间分成两部分，并检查是否

例子

// 实现线性搜索的函数 
function findCeiling(arr, l, h, x){

   //定义结束条件
   if(x <= arr[l]){
      return l;
   }
   else if(x > arr[h]){
      return -1;
   }    
   var mid = (l + h)/2;   

   //如果当前元素和x相同，返回当前索引 
   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);
      }
   }
}

//定义数组 
var arr = [1, 2, 4, 5, 8, 19, 25]
var num = 15
console.log("给定的数组是: ");
console.log(arr);

//调用函数 
var idx = findCeiling(arr,0, arr.length-1, num);
if(idx == -1){
   console.log("给定数字" + num + "的上限不存在");
}
else{
   console.log("给定数字" + num + "在数组中的上限是" + arr[idx]);
}
num = 78
idx = findCeiling(arr, 0, arr.length-1, num);
if(idx == -1){
   console.log("给定数字" + num + "的上限不存在");
}
else{
   console.log("给定数字" + num + "在数组中的上限是" + arr[idx]);
}

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

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