二分查找（折半查找）探究学习

1.引入

 当我们想要查找在一个数组中某一个特定的数它的下标是什么的时候，我们最先想的方法是遍历数组，如下：

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

  但是这种查找方法有一定的局限性，因为如果当它数字很大的时候，我们便需要一个一个校对，对计算机的工作量比较大。

  ⽐如我买了⼀双鞋，你好奇问我多少钱，我说不超过300元。你还是好奇，你想知道到底多少，我就让你猜，你会怎么猜？你会1，2，3，4...这样猜吗？显然很慢；⼀般你都会猜中间数字，⽐如：150，然后看⼤了还是小了，这就是⼆分查找，也叫折半查找。

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

a.所给的数组应该已经按照升序或者降序排列好了。

b.确定被查找范围的左右下标。

c.根据左右下标确定中间元素和要找的元素进行比较。

{找到了，就结束}

{找不到，依据大小关系，确定新的查找范围}

d.根据左右下标确定中间元素的下标。

#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;//要找的数字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");
}