之前說過，二分法算法是一種非常常見的算法。這里大概說說算法的內(nèi)容。具體算法如果有興趣，去百度、維基百科，搜搜就都能找到。我就不做搬運(yùn)工了。這里就我個(gè)人的理解，不嚴(yán)謹(jǐn)?shù)恼f說。
在排序好的一列大小為n的數(shù)組A[]，找數(shù)字num。設(shè)left=0，right=n-1：
while(left<=right){
mid = (left + right)/2;
if (A[mid] == num) return mid;
if (A[mid] < num) left = mid + 1;
if (A[mid] > num) right = mid - 1;
}
return -1;
這里面 mid是我們找的中間點(diǎn)。如果正好找到了，那就直接返回不用繼續(xù)找了。如果num比中間點(diǎn)的數(shù)大，那左邊就移動(dòng)到中間點(diǎn)的右邊。這樣搜索的范圍就小了一半。反之，則把右邊移到中間點(diǎn)的左邊。
最終如果已經(jīng)搜素過了整個(gè)范圍，left已經(jīng)大于right，我們還沒有找到num，那就是這個(gè)數(shù)組里沒有這個(gè)數(shù)。這里我用一個(gè)數(shù)組里并不存在的index，-1，來表示。
這個(gè)看起來簡單，但在實(shí)際的實(shí)現(xiàn)中，還有很多要注意的地方，這個(gè)以后有機(jī)會(huì)再說。
總之，上面已經(jīng)給出了了最基本的二分法搜索算法：通過每次重新界定左右邊界來縮小一半的搜索范圍。
