二分查找法的實現和應用匯總

), 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) 




，我們很難保證我們的數組都是有序的。當然可以在構建數組的時候進行排序，可是又落到了第二個瓶頸上：它必須是數組。