折半查找(二分法)

时间:2021-12-28 22:10:27

适用场合: 数据有序是前提。
//////////////////////
#include <stdio.h>
int Search_by_half(int *p,int n,int data)
{
 int start = 0,end = n-1,mid;
 
 while(start <= end)
 {
  mid = (start+end)/2;
  if (data == p[mid])
   return mid;
  
  else if(data < p[mid])
   end = mid-1;
  else
   start = mid+1;
 }
 return -1;
}

二分查找:给定数组是有序的,给定一个key值。每次查找最中间的值,如果相等,就返回对应下标,如果key大于最中间的值,则在数组的右半边继续查找,如果小于,则在数组左半边查找,。最终有两种结果,一种是找到并返回下标,第二种是没找到。

下面给个例子说明一下:

有一个数组arr[10];

   0      1      2      3      4       5      6       7      8       9 

3

6

7

10

11

16

20

33

56

89

定义两个边界下标low和high,定义中间下标mid;

low=0; high=10-1; mid = (low+high)/2;

在进行每一步的比较时,low<=high;

如果我们寻找key为56的值的下标。

第一次我们找到中间下标mid = 4;

    0      1      2      3      4       5      6       7      8       9   

3

6

7

10

11

16

20

33

56

89

  low                                 mid                                          high

arr[4] = 11,比当前key值小,所以我们在右半边查找,令low = mid + 1;high不变;

我们找到中间下标mid = (5+9)/2 =7;

    0      1      2      3      4       5      6       7      8       9                                       

3

6

7

10

11

16

20

33

56

89

                                 low                       mid             high

arr[7] = 33,比当前key值小,所以我们在右半边查找,令low = mid + 1;high不变;

我们找到中间下标mid = (8+9)/2 =8;

    0      1      2      3      4       5      6       7      8       9                                                     

3

6

7

10

11

16

20

33

56

89

                                              low   high

                      mid

此时key == arr[mid] == arr[8];停止查找,返回下标mid;

 

所以在查找56的时候,比较次数为3次。


int main()
{
 int a[12] = {3,12,18,20,32,55,60,68,80,86,90,100};
 int x = Search_by_half(a,12,85);
 if(x == -1)
  printf("Not found!\n");
 else
  printf("Pos : %d\n",x);
 return 0;
}