❶ 數據結構怎樣折半查找
舉個例子說明吧，在下面一堆數中找數字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指向後半部分的第一個下標),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止.