二分查找
??二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法，但是，折半查找要求線性表必須采用順序存盤結構，而且表中元素按關鍵字有序排列，如果要查找的元素在表中，那么回傳它，如果元素不在表中，回傳NULL，
順序查找與二分查找的比較
為什么說二分查找是一種效率較高的查找方法呢？
首先我們來看看順序查找，舉個例子，
比如我們有：
??????3，6，9，11，12，15，19，20，22，
這九個數字，
?? 我隨便選擇其中的一個數字，假設是11，我們要從這九個數字中找到11，如果找到的數字是11，那就找到了，如果這九個數中沒有11，那就找不到，
?? 假設從第一個開始找，
第一次：3，不對
第二次：6，不對
第三次：9，不對
第四次：11，找到了！
?? 這就是順序查找，每次尋找只能排除一個數字，現在我們要找的是11，只要四次，可是如果我們要找的是25，就要九次了，如果數字的個數更多那就要花費更多次數，
那么效率較高的二分查找是怎樣的呢？
??假設我們要找的數字仍然是11，
第一次：我們取這九個數字的中間的數字：12，11<12，小了，那么我們就能排除12右邊的部分，
第二次：我們取12左邊部分的中間的數字：9，11>9，大了，那么我們就能排除9左邊的部分，
第三次：我們取9右邊部分的中間數字：11，11=11，找到了，
?? 這樣的方式要比上面的順序查找快得多，可能在這個例子中只有一次的差別，可當數字多了呢？那二分查找的速度就要快的多了，這就是二分查找，
使用
下面來看看二分查找在c語言中的運用，這里我使用的是VS2013，
#include <stdio.h>
int main()
{
char arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//tofind表示要找的數字
int tofind = 7;
//陣列最左邊元素的下標
int left = 0;
//陣列最右邊元素的下標
int right = sizeof(arr) / sizeof(arr[0]) - 1;
//sizeof(arr)是計算arr的位元組
//sizeof(arr[0])是計算陣列中第一個的位元組
//兩者相除就是陣列長度
while (left <= right){
int mid = (left + right) / 2;
if (tofind > arr[mid]){
//說明你要查找的數在mid 的右邊，
//因此需要向右遞回查找
left = mid + 1;
}
else if (tofind < arr[mid]){
right = mid - 1;
}
else{
printf("找到了，下標是：%d\n", mid);
break;
}
}
if (left>right){
printf("找不到");
}
system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/181413.html
標籤：其他
上一篇：如何提升香港服務器運用效率