折半查找法(C語言折半查找法如何使用)

1. 折半查找介紹

1.1 定義

折半查找也稱二分查找,是一種在有序數組中查找某一特定元素的搜索算法,每一次查找,搜索范圍均縮小一半,效率較高。如果數組是亂序狀態,則應排序,再進行查找。

1.2 基本原理

搜索過程從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜索過程結束;如果某一特定元素大于或者小于中間元素,則在數組大于或小于中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空,則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半 。

1.3 時間復雜度與空間復雜度

總共有n個元素,每次查找的區間大小就是n,n/2,n/4,…,n/ 2 k 2^k 2k,一直到1,其中k就是循環的次數。

由于n/ 2 k 2 ^ k 2k取整后>=1,即令n/ 2 k 2^k 2k=1,可得k=log2n,(是以2為底,n的對數),所以時間復雜度可以表示O()=O(logn)。

二分查找只需要額外存儲三個變量:最大值 ,最小值 和 中點,空間復雜度為常數 O(1)。

1.4 優缺點

優點:比較次數少,查找速度快,平均性能好。

缺點:要求待查表為有序表,且插入刪除困難。

2. 代碼實現

2.1 代碼設計

1. 輸入需要查找的元素,我們輸入的是38;left是有序數組最左端0,是最小值,right是有序數組最右端10,是最大值,mid為數組1/2位置,即array[5];

2. 38比array[5] = 19大,因此left等于原mid+1,即array[6] = 26,right不變;新mid為(left+right)/2 = (6+10)/2 = 8;

3. 38比array[8] = 36大,因此left等于上一次mid+1,即array[9] = 38,right不變;新mid為(left+right)/2 = (9+10)/2 = 9;

4. 38等于array[9],mid與left重合, 查找成功,返回數組下標9.

2.2 代碼實現

#include<stdio.h>#include<string.h>intbinarySearch(intarray[],intlen,inttarget){intleft=0;intright=len-1;while(left<=right){intmid=(right+left)/2;if(array[mid]==target){returnmid;}elseif(array[mid]<target){left=mid+1;}elseif(array[mid]>target){right=mid-1;}}return-1;}intmain(void){intarray[]={2,3,4,5,15,19,26,27,36,38,45};intkey=0,ret;printf("請輸入需要查找的數字:");scanf("%d",&key);ret=binarySearch(array,sizeof(array)/sizeof(int),key);if(ret<0)printf("查找失敗\n");elseprintf("該數字為數組第%d個元素\n",ret+1);return0;}

運行結果:

請輸入需要查找的數字:38

該數字為數組第10個元素

以上就是關于“C語言折半查找法如何使用”這篇文章的內容,相信大家都有了一定的了解,希望小編分享的內容對大家有幫助,若想了解更多相關的知識內容,請關注本站行業資訊頻道。