), O(n), O(2)
)。但是也正是因為有二分的 O(log n), 才讓很多 O(n)縮減到只要O(n log n)。
bsearch( array[], low, high, target)
假如從性能上考慮,也可以寫成這樣:
int binary_search(int array[] , int len , int value) { int left = 0; int right = len - 1; while(left <= right){ int middle = left + ((right - left) >> 1); if(array[middle] > value){ right = middle - 1; } else if(array[middle] < value){ left = middle + 1; } else return middle; } return -1; }
#include<iostream> using namespace std; int binary_search(int array[] , int len , int value) { int left = 0; int right = len - 1; while(left <= right){ int middle = left + ((right - left) >> 1); if(array[middle] > value){ right = middle - 1; } else if(array[middle] < value){ left = middle + 1; } else return middle; } return -1; } int main() { int array[4] = {1 , 4 , 5 , 7}; cout<<binary_search(array , 4 , 5)<<endl; system("pause"); return 0; }
bsearchWithoutRecursion( array[], low, high, target)
BSearch(T& array, low, high, V& target)
中找到“正好大於(小於)目標數”的那個數。
array = {, , , , , , };
BSearchUpperBound( array[], low, high, target)
,,(目標數)。而界限查找則分成了兩類:和。
BSearchLowerBound( array[], low, high, target)
,也就是要或者。如果要找松散界限,也就是找到或者的值(即包含自身),只要對代碼稍作修改就好了:
target >= array[high]改為 target > array[high]
array[mid] > target改為array[mid] >= target
。假如存在重復數據,而數組依然有序,那麼我們還是可以用二分查找法判別目標數是否存在。不過,返回的index就只能是隨機的重復數據中的某一個。
, > SearchRange( A[], n, target)
的數組上,如果是無序的,那麼比較和二分就沒有意義了。
SearchInRotatedSortedArray( array[], low, high, target)
,我們很難保證我們的數組都是有序的。當然可以在構建數組的時候進行排序,可是又落到了第二個瓶頸上:它必須是數組。