1.引入

?當(dāng)我們想要查找在一個數(shù)組中某一個特定的數(shù)它的下標(biāo)是什么的時候，我們最先想的方法是遍歷數(shù)組，如下：

#include<stdio.h>
#include<string.h>
int main()
{
int arr[10]={1,2,3,4,5,6,7,8,9,10};
int key = 8;//要找的數(shù)是8
for(int i=0;i<10;i++)
{
if(arr[i]==key)
{
printf("找到了，下標(biāo)為%d\n",i);
break;
}
}
return 0;
}

? 但是這種查找方法有一定的局限性，因為如果當(dāng)它數(shù)字很大的時候，我們便需要一個一個校對，對計算機(jī)的工作量比較大。

2.折半查找的要求以及其作用

a.所給的數(shù)組應(yīng)該已經(jīng)按照升序或者降序排列好了。

b.確定被查找范圍的左右下標(biāo)。

c.根據(jù)左右下標(biāo)確定中間元素和要找的元素進(jìn)行比較。

{找到了，就結(jié)束}

{找不到，依據(jù)大小關(guān)系，確定新的查找范圍}

d.根據(jù)左右下標(biāo)確定中間元素的下標(biāo)。

#include <stdio.h>
int main()
{int arr[] = {1,2,3,4,5,6,7,8,9,10};int left = 0;int right = sizeof(arr)/sizeof(arr[0])-1;int key = 7;//要找的數(shù)字int mid = 0;//記錄中間元素的下標(biāo)int find = 0;while(left<=right){mid = (left+right)/2;if(arr[mid]>key){right = mid-1;}else if(arr[mid] < key){left = mid+1;}else{find = 1;break;}}if(1 == find )printf("找到了,下標(biāo)是%d\n", mid);elseprintf("找不到\n");
}