排序陣列中查詢上限的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程式，用於為給定的排序陣列查詢給定數字的上限。給定數字的上限是查詢存在於給定陣列中且等於給定數字的數字，如果不存在，則查詢大於給定數字的數字。如果給定陣列中沒有一個元素大於給定數字，則它不存在。我們已經實現了線性搜尋和二分搜尋演算法。