目錄
一、實作原理
二、圖解分析
三、編程實作
一、實作原理
引理：
相信大家都玩過這樣一個游戲，猜數字游戲，
游戲規則：隨機寫出一個1-100以內的數，讓我們去猜這個數多少，每猜一次裁判員都會有提示，是否猜中，猜的數比被猜數的大小關系，
例如：寫出一個56
第一次猜：猜50 提示：比被猜數小
第二次猜：猜75 提示：比被猜數大
第三次猜：猜62 提示：比被猜數大
第四次猜：猜56 提示：猜中了
以上查找的方法使用的就是二分查找，你看懂了嗎？
就這！！！
二分查找的要求：待查陣列是有序的
二、圖解分析
舉例：有這樣一個陣列，如圖下，
我們先將Key和arr[mid]數做比較，
如果Key==arr[mid]，那么就找到了，
如果Key>arr[mid],說明查找的數可能在[mid+1,right]之間
如果Key<arr[mid],說明要查找的數可能在[left,mid-1]之間
那么從上圖陣列中我們來找一找Key=9
第一次查找：
mid=(left+right)/2
arr[mid]<Key
left=mid+1;
第二次查找：
mid=(left+right)/2
arr[mid]>Key
right=mid-1
第三次查找：
mid=(right+mid)/2
arr[mid]==Key
查找結束，
例子2：我想在里面查找18
第一次查找：
mid=(left+right)/2
arr[mid]<Key
left=mid+1;
第二次查找：
mid=(left+right)/2
arr[mid]<Key
left=mid+1;
第三次查找：
mid=(right+left)/2
arr[mid]<Key
left=mid+1
第四次查找：
mid=(left+right)/2
Key>arr[mid]
left=mid+1
我們可以看到left>right那么還有繼續查找的必要嗎？
當然沒有，因為陣列是有序的，沒有既大于left左邊的數同時又大于right右邊的數，所以此陣列中沒有這個數，
看到這里是不是覺得很簡單呀？Easy!!!
三、編程實作
//找到了回傳陣列下標，找不到回傳-1
int BinarySearch(int *arr,int Key,int n){
int left=0;
int right=n-1;
while(left<=right){//left>right則找不到，
int mid=(right+left)/2;//中間數
if(arr[mid]==Key)
return mid;
else if(arr[mid]<Key)//條件成立查找區間改變到[mid+1,right]
left=mid+1;
else
right=mid-1;//否則查找區間改變到[left,mid-1]
}
return -1;//找不到回傳-1
}
鄙人不才，勿噴，看懂的可以留個小愛心，
再見！！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/385426.html
標籤：其他