許多二分查找實作中的一個問題？

我們知道二分搜尋演算法比線性搜尋演算法更好。此演算法執行所需的時間為O(log n)。儘管大多數情況下，實現的程式碼存在一些問題。讓我們來考慮一個二分搜尋演算法函數，如下所示 −

範例

int binarySearch(int array[], int start, int end, int key){
   if(start <= end){
      int mid = (start + end) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

這個演算法在開始和結束達到一個較大的數之前都能正常運作。如果 (開始 結束) 超過了 2³² - 1 的值，那麼在包裝後可能會傳回一個負數。由於負數不支援作為數組索引，所以可能會引起一些問題。

為了解決這個問題，有幾種不同的方法。

方法1

int mid = start + ((end - start) / 2)

第二種方法只適用於Java，因為C或C 沒有>>>運算子。

方法2（只適用於Java）

int mid = (start + end) >>> 1

由於C或C 不支援>>>，我們可以使用下列方法。

方法3

int mid = ((unsigned int) low + (unsigned int) high) >> 1

#

以上是許多二分查找實作中的一個問題？的詳細內容。更多資訊請關注PHP中文網其他相關文章！