快捷導(dǎo)航

C語(yǔ)言二分查找算法及實(shí)現(xiàn)代碼

更新時(shí)間：2016年07月18日 16:39:08 投稿：lqh

本文主要介紹C語(yǔ)言的二分查找算法,這里給大家詳細(xì)介紹了什么是二分查找,并提供代碼實(shí)例,需要的小伙伴可以參考下

二分査找也稱(chēng)折半査找，其優(yōu)點(diǎn)是查找速度快，缺點(diǎn)是要求所要査找的數(shù)據(jù)必須是有序序列。該算法的基本思想是將所要査找的序列的中間位置的數(shù)據(jù)與所要査找的元素進(jìn)行比較，如果相等，則表示査找成功，否則將以該位置為基準(zhǔn)將所要査找的序列分為左右兩部分。接下來(lái)根據(jù)所要査找序列的升降序規(guī)律及中間元素與所查找元素的大小關(guān)系，來(lái)選擇所要査找元素可能存在的那部分序列，對(duì)其采用同樣的方法進(jìn)行査找，直至能夠確定所要查找的元素是否存在，具體的使用方法可通過(guò)下面的代碼具體了解。

#include <stdio.h>
binarySearch(int a[], int n, int key){
 int low = 0;
 int high = n - 1;
 while(low<= high){
  int mid = (low + high)/2;
  int midVal = a[mid];
  if(midVal<key)
   low = mid + 1;
  else if(midVal>key)
   high = mid - 1;
  else
   return mid;
 }
 return -1;
}
int main(){
 int i, val, ret;
 int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};
 for(i=0; i<8; i++)
  printf("%d\t", a[i]);
 printf("\n請(qǐng)輸人所要查找的元素：");
 scanf("%d",&val);
 ret = binarySearch(a,8,val);
 if(-1 == ret)
  printf("查找失敗 \n");
 else
  printf ("查找成功 \n");
 return 0;
}

運(yùn)行結(jié)果：

-32 12 16 24 36 45 59 98

請(qǐng)輸入所要查找的元素：12

查找成功

在上面的代碼中，我們成功地通過(guò)二分査找算法實(shí)現(xiàn)了查找功能，其實(shí)現(xiàn)過(guò)程如下圖所示。

在如上圖所示的查找過(guò)程中，先將序列中間位置的元素與所要査找的元素進(jìn)行比較，發(fā)現(xiàn)要査找的元素位干該位置的左部分序列中。接下來(lái)將mid的左邊一個(gè)元素作為 high，繼續(xù)進(jìn)行二分査找，這時(shí)mid所對(duì)應(yīng)的中間元素剛好是所要査找的元素，査找結(jié)束，返回査找元素所對(duì)應(yīng)的下標(biāo)。在main函數(shù)中通過(guò)返回值來(lái)判斷査找是否成功，如果査找成功.就打印輸出“査找成功”的信息，否則輸出“査找失畋”的信息。

以上就是對(duì)二分查找法的詳細(xì)介紹，希望學(xué)習(xí) C語(yǔ)言的同學(xué)可以掌握。

您可能感興趣的文章: