折半查找思想

1、基本思路

在有序序列中,取中间元素作为比较对象,若给定值与中间元素的要查找的数相等,则查找

成功;若给定值小于中间元素的要查找的数,则在中间元素的左半区继续查找;

若给定值大于中间元素的要查找的数,则在中间元素的右半区继续查找。

不断重复上述查找过 程,直到查找成功,或所查找的区域无数据元素,查找失败。

2、实现步骤

【步骤】

1 min=0;max=len-1;// 设置初始区间

2 当min>max 时,返回查找失败信息// 表空,查找失败

3 min≤max,mid=(min+max)/2; //取中点

a.b.c进入循环

a. 若key

b. 若key>arr[mid],min=mid+1;转2 // 查找在右半区进行

c. 若key=arr[mid],返回数据元素在表中位置//查找成功

折半查找代码实现:

 输入一组有序数据,使用折半查找法查找一个数据,并输出其位 置。

intserach(intarr[],int len,int key){

int min =0;

int max = len-1;

for(int i=0; i < len; ++i) {

printf("%d \t",arr[i]);

}

printf("\n");

while(min<=max) {

intmid = (max+min)/2;

if(arr[mid]>key) {

max = mid-1;

}else if(arr[mid]

min = mid+1; }else{

returnmid;

}

}