c语言-二分查找法（数组）

题目详情

用二分法在一个有序数列{1,2,3,4,5,6,7,8,9,10}中查找key值，若找到key则输出其在数组中对应的下标，否则输出not found。

---

文章目录

• 
  

  一、输入样例

• 
  

  二、输出样例

• 
  

  三、代码展示

• 
  

  四、思路体现

• 
  

  五、难点记录 

---

一、输入样例

直接输入一个要查找的正整数key。

没有其它任何附加字符。

1）第一个输入样例

4

 2）第二个输入样例

15

---

二、输出样例

找到则在一行中按照“weizhi:下标”的格式输出其在数组中对应的下标，否则输出not found。

1）第一个输出样例

weizhi:3

2）第二个输出样例

not found

---

三、代码展示

#include
int main()
{
	int a[10]={1,2,3,4,5,6,7,8,9,10};       //定义初始数组
	int i,key,index1,index2,mid;        //key：准备查找的值；index1：最小下标；index2：最大下标；mid：中间值下标
	scanf("%d",&key);       //输入要查找的正整数key
	for(index1=0,index2=9;index1<=index2;){     //通过for循环进行查找，
		mid=(index1+index2)/2;
		if(key==a[mid]){
			printf("weizhi:%d",mid);        //若是找到key的话，直接break结束循环
			break;
		}else if(keyindex2)printf("not found");
}

---

四、思路体现

设n个元素的数组a已升序排列，用index1和index2两个变量来表示查找的区间，即在a[index1] 〜 a[index2]区间去查找key。

初始状态为index1=0，index2=n-1。

首先用要查找的key与查找区间的中间位置元素a[mid]（mid = (index1 + index2) / 2）比较，如果相等则找到；如果x < a[mid]，由于数组是升序排列的，则只要在a[index1] 〜 a[mid-1]区间继续查找；如果x > a[mid]，则只要在a[mid+1] 〜 a[index2]区间继续查找。

也就是根据与中间元素比较的情况产生了新的区间值index1、index2值，当出现index1 > index2时，说明不存在值为key的元素。

五、难点记录

不了解二分查找法的特点；