---

二分查詢

  二分查詢也稱折半查詢（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;
}