算法篇——二分查找

二分查找也稱折半查找，顧名思義，把一數組不斷地折半來查找。

1.條件：有序，有序，有序（重要的事情說三遍）

2.思路：查找元素的值與中間元素的值不斷比較，來標明區間，生成新的數組。

如：在a[]={1,2,3,4,5,6,7,8,9,10}中找到“6”。

第一次折半：取得數組a[]中間值“5”（不整除将向下取整） (找中值)，“5”<“6”（比較），是以選擇後半部份元素 （選區間） ，産生新數組為a1[]={6,7,8,9,10} （新數組）。

第二次折半：取得數組a1[]中間值“8” (找中值)，“8”>“6”（比較），是以選擇前半部份元素 （選區間），産生新數組為a2[]={6,7} （新數組）。

第三次折半：取得數組a2[]中間值“6”，即為所查找元素。

類似于猜數字遊戲，（1）1-100（25為謎底），先猜50，比較可知，猜大了，要往小一點的數字猜，把1-49再折一半，得25。（2）1-100（75為謎底），先猜50，比較可知，猜小了，要往大一點的數字猜，把51-100再折一半，得75。

3.優點:加快查找效率（剛開始我也不覺得效率有多快，可面對上萬元素時，一次折半就可以過濾掉一半元素，才覺得這方法運用起來還是不賴的）。

4.查找次數

5.代碼示範

#include<stdio.h>

void search(int a[], int n, int key)
{
	int low = 0; //數組第一個位置
 	int high = n - 1; //數組最後一個元素
 	int mid; //中間值
 	int counter = 0; //查找次數
	while(low <= high)
	{
  		counter++; //累加次數
  		mid = (low + high) / 2; //如果（low+high）不是偶數，mid将向下取整
  		if(a[mid] <= key)//選擇後區間為新區間
  		{
   			low = mid + 1; //把中間元素後面的一個元素當新區間的首元素
 		}
  		if(a[mid] >= key) //選擇前區間為新區間
  		{
   			high = mid - 1; //把中間元素前面的一個元素當新區間的尾元素
  		}
  		if (a[mid] == key)//找到該元素
  		{
   			printf("該值位置為:%d\n", mid + 1);
  		}
 	}
 	printf("查找次數為:%d\n", counter);
}
int main()
{
 	int a[] = {1,2,3,4,5,6,7,8,9,10};
 	int n = (sizeof(a) / sizeof(int));
 	int key = 6;
 	search(a,n,key);
 	return 0; 
}