對於找不到元素的二進制搜索，如何返回它應該插入的索引

Question

我想使用二進制搜索來查找元素應該放置的數組索引。這是爲了將元素插入到陣列中，同時向下移動較大的元素。如何修改這個二進制搜索以指定未找到的元素應該放置的位置？

int binarySearch(int arr[], int x) { 

     int low = 0; 
     int mid = 0; 
     int high = arr.length - 1; 
     while (low <= high) { 
      mid = (low + high)/2; 
      if (x < arr[mid]) { 
       high = mid - 1; 
      } else if (x > arr[mid]) { 
       low = mid + 1; 
      } else { 
       return mid; 
      } 
     } 
     //This is what im trying to get to work 
     if (x < arr[mid]) { 
      return high; 
     } else { 
      return low; 
     } 
    } 

謝謝。

Answer 1

看看java.util.Arrays.binarySearch（）如何執行它。

Answer 2

Arrays.binarySearch（）返回-(insertion_point + 1)。這樣，返回值≥0是匹配，返回值< 0未命中，insertion_point = -return_value - 1。

Answer 3

查看C++標準模板庫中的lower_bound和upper_bound。這些鏈接符合規範;該實現位於同一網站的實現部分中的stl_algo.h文件中，但是我是新用戶，因此一次不能發佈兩個以上的URL。