假如我們在圖書館中整理書記，書按照序號有序排序，序號不連續(xù)，當(dāng)我們需要從書堆中找到特定序號的書時，如果一本一本查找的話，我們可能需要查找N次。但如果我們先找到中間的書，將書分成兩堆，與待查書對比，待查書序號較大的時候從序號大的一堆中在分成兩堆繼續(xù)對比，書號小時從小的那堆繼續(xù)對比，直到找到對應(yīng)書號，這樣只需查找log2(n)次。
這就是二分查找法。
例如我們有一個被排序好的數(shù)組
int a[10] = {1,3,5,7,9,11,13,15,17,19};
我們需要在其中找到13的下標(biāo)
如果采用二分法：

與中間值9進(jìn)行對比，比9大，取左邊。

與中間值13進(jìn)行對比，比9小，取右邊。

與中間值13對比，相同，返回下標(biāo)。
完成這個算法，我們首先需要知道左右兩邊的下標(biāo)和中間的下標(biāo)。
起始時左邊下標(biāo)為0，右邊為數(shù)組最后一項下標(biāo)，中間下標(biāo)為兩者的平均值。

right = sizeof(arr)/sizeof(arr[0])-1;left =0;mid = (right + left) / 2;

因為我們需要進(jìn)行多次的對比，所以需要在一個循環(huán)中進(jìn)行，每次對比完后，如果比中間值大，則把左邊下標(biāo)改為中間值+1，如果比中間值小，則把右邊下標(biāo)改為中間值-1

while(left <= right){mid = (right + left) / 2;if( n > arr[mid] ){left = mid + 1; } else if( n < arr[mid]){right = mid - 1;}else if( n == arr[mid]){return mid;}}

當(dāng)左邊下標(biāo)小于等于右邊下標(biāo)時執(zhí)行循環(huán)，而當(dāng)跳出循環(huán)后左邊下標(biāo)大于右邊下標(biāo)時說明該數(shù)據(jù)不存在，返回一個-1，如果正確則返回下標(biāo)。

if(left > right){return -1;}

最后在主函數(shù)中用一個數(shù)對下標(biāo)進(jìn)行判斷，如果下標(biāo)為-1時，說明數(shù)據(jù)不存在，因為下標(biāo)不可能<0;

if( -1 == mid ){printf("查找失敗 "); }else{printf("下標(biāo)為：%d",mid);}

運行效果：

---

完整代碼：

#include<stdio.h> int Binary_Search(int right,int n,int arr[]) {int left =0,mid;while(left <= right){mid = (right + left) / 2;if( n > arr[mid] ){left = mid + 1; } else if( n < arr[mid]){right = mid - 1;}else if( n == arr[mid]){return mid;}}if(left > right){return -1;} } int main() {int arr[] ={1,3,5,7,9,11,13,15,17,19};int n,i,right,left,mid;right = sizeof(arr)/sizeof(arr[0])-1;left =0;printf("請輸入要查找的數(shù)據(jù):");scanf("%d",&n);mid = Binary_Search(right,n,arr);if( -1 == mid ){printf("查找失敗 "); }else{printf("下標(biāo)為：%d",mid);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法 | 二分查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。