1.引入

?當我們想要查找在一個數(shù)組中某一個特定的數(shù)它的下標是什么的時候，我們最先想的方法是遍歷數(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("找到了，下標為%d\n",i);
break;
}
}
return 0;
}

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

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

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

b.確定被查找范圍的左右下標。

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

{找到了，就結束}

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

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

#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;//記錄中間元素的下標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("找到了,下標是%d\n", mid);elseprintf("找不到\n");
}