❶ 数据结构怎样折半查找
举个例子说明吧，在下面一堆数中找数字2
编写代码是先定义3个int类型的变量m，f，l，
初始时，将f==1的地址，l==7的地址，m=（f+l）/2
先遍历m处的数据，它大于2，说明2在它的左边，这个时候将l的值改一下，改成l=m-1（为什么呢？因为你把l改成m-1，那么下一次遍历就在1到4之间查找了。）
l=m-1，f=1不变，m等于此时的l加f的和除以2，即m=（f+l）/2，那么m就指向（1+4）/2=2.5的位置，但是m是int类型，在c中2.5取整后为2，所以m=2，m指向数组第二个位置，这个位置的数据就是2，查找成功！
初始时：
f=First m=Middle l=last
↓ ↓ ↓
1 2 3 4 5 6 7
第二次遍历：
f m l
↓ ↓ ↓
1 2 3 4 5 6 7
❷ 数据结构折半查找算法的方法
#include<stdio.h>
intDichotomy(inta[],int_value,intn){//二分法(也称折半查找法)
intindex=0;//当前数组的首元素下标
intcurrent=n-1;//数组当前的大小
intk;//当前数组中间的数的下标
while(index<current)
{
//开始二分法查找
k=(index+current)/2;//除以2代表得到当前数组中间的数的下标
if(a[k]==_value)returnk;//返回要查找的值_value所在的下标
//否则比较要查找的值_value是在折半后的前半部分还是后半部分
if(a[k]<_value){//说明要查找的值在折半后的后半部分
index=k+1;//令index指向后半部分数组的首元素
}
else{//说明要查找的值在折半后的前半部分
current=k-1;//令current等于前半部分数组的长度
}
}
return-1;//返回-1代表没有查找到该值(_value)
}
voidmain(){
intarr[5]={2,12,45,87,95};//前提是一组数组必须是有序数对(即按小到大或大到小)
if(Dichotomy(arr,87,5)!=-1)
printf("87在数组中对应的下标是:%d ",Dichotomy(arr,87,5));
elseprintf("没有找到指定的值 ");
}
//用一句话概括二分法(折半查找法)的思想就是:在一组有序对数组中反复折半后得到中间数组的下标,然后再进行是否与要查找的值相等,若相等则返回当前要查找的值的下标。
那么，上面的代码的注释与下面一一对应，它在执行的结果会产生两种情况，第一种,不存在。第二种，存在。
先来说说第一种情况不存在：
1.如果给定要查找的值_value大于数组中最大的数,则index不断增大从而促使while循环终止2.如果给定要查找的值_value小于数组中最小的数,则current不断减少从而促使while循环终止(你自己可以动手在纸上画一个数组,然后思路跟着代码走就会知道或设单步调试亦可)
第二种情况存在：
1.要查找的数_value正好是在数组中间.那么就执行了一次循环,当然这也是最理想的效果.
否则反复执行2和3:
2.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果小于中间的数则说明_value应该在数组中间的前半部分,那么current=k-1(即令current等于前半部分的长度),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止.
3.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果大于中间的数则说明_value应该在数组中间的后半部分,那么index=k+1(即令index指向后半部分的第一个下标),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止.