二分法的查找图解

时间:2021-12-24 22:11:09

最近做了几家笔试题,基本在选择题都考到二分查找法的次数。由于对下标和数组大小的不确定,做错了好几个,今天,希望通过图解来说明一下二分查找的比较次数。

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

下面给个例子说明一下:

有一个数组arr[10];

   0      1      2      3      4       5      6       7      8       9 

3

6

7

10

11

16

20

33

56

89

定义两个边界下标lowhigh,定义中间下标mid

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

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

如果我们寻找key56的值的下标。

第一次我们找到中间下标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 + 1high不变;

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

    0      1      2      3      4       5      6           8       9                                       

3

6

7

10

11

16

20

33

56

89

                                 low                       mid             high

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

我们找到中间下标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 search(int arr[],int n,int key)
{
   int low = 0,high = n-1;
   int mid,count=0;
   while(low<=high)
   {
      mid = (low+high)/2;
      if(arr[mid] == key)
         return mid;
      if(arr[mid]<key)
         low = mid + 1;
      else
         high = mid - 1;
   }
   return -1;
}