二分查找之深入分析

小鱼儿 2022-05-23 20:45 175阅读 0赞

二分搜索算法是运用分治法的经典例子，给定已排好序的n个元素，现在要在这n个元素中找到一个特定的素，注意使用二分查找的时候要知道已排序的n个元素是升序还是降序还有你使用的数据类型（字符串类型的比较要注意）。

1. 最基础的二分查找

下面的的例子为升序情况的二分查找的情况。

示例：如有已排序数组有8个元素如下查找元素x = 5;

1  5  6  7  9  10  12 44

将数组分为两个子段(0+7)/2 = 3： 1  5  6  7  9  10  12 44

比较array\[4\] = 7与x = 5的大小由于数组为升序：

（1）若分段点元素大于x，则不用查找分段点以后的元素；

（2）若分段点元素小于x，则不用查找分段前之前的元素；

（3）若分段点元素等于x表示已找到该元素，返回。

array\[4\]比x大，则查找array\[4\]之前的元素，将array\[4\]之前的看作一个子数组继续进行二分操作。

2.改进二分查找--若查找的元素出现多次查找第一次出现的位置

我们可以从第一次得代码中知道，上述代码不能确定查找到得元素的位置为第一次出现的位置。怎么确定查找的元素在该序列中出现的是第一次呢，我们举一个例：

数组：1  2  3  3  3  3  3  5 ；8个元素，查找值为3的元素。

将数组分为两个子段(0+7)/2 = 3： 1  2  3  3  3  3  3  5

此时已查找到3，一种简单的实现方法可以在从该位置开始向前搜索，找到直到不等于3的时候就停止，这个时候找到3的位置就是第一次出现的位置，同理我们也可以用这种方法找到最后出现的3的位置。

<table style="line-height:18px; text-align:left; background-color:rgb(255,240,209); color:rgb(0,0,0); font-family:宋体,Arial; font-size:12px; padding:0pt; margin-left:1.7pt; border-collapse:collapse"> 
 <tbody style="line-height:21px"> 
 <tr> 
 <td colspan="2" style="line-height:1.5; padding:0pt; width:338.15pt"> 语法：result=search_bin(int&nbsp;*t,int&nbsp;k,int&nbsp;n); </td> 
 </tr> 
 <tr style="height:16.35pt"> 
 <td colspan="2" style="line-height:1.5; padding:0pt; width:338.15pt"> 参数： </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> t[]： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 待查找数组 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> k： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 查找关键字 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> n： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 数组元素个数 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 返回值： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 如果k在t[]中存在，输出i,i为k在t[]中第一次出现的位置：t[i]=k，否则输出－1 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 注意： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> &nbsp;数组元素从0开始存储 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> &nbsp; </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 要求查找数组是有序升序序列 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 源程序： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> &nbsp; </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> int&nbsp;search_bin(int&nbsp;*t,int&nbsp;k,int&nbsp;n) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;low=0,high=n-1,mid; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(low&lt;=high) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mid=(low+high)/2; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(k==t[mid])&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(t[mid] ==&nbsp;k) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mid--; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;mid+1; &nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;(k&lt;t[mid])&nbsp;high=mid-1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;low=mid+1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;-1; } </td> 
 </tr> 
 </tbody> 
</table>

我们通过上面的代码也许可以知道，这样实现确实很简单，但是这样效率确实降低了，如果有一个极端的例子，即一个数组里面的元素全部相同，且我们要查找的元素就是该数组的元素此时在查找第一个出现位置的时候就比较消耗时间，这里我们可以深入一点，继续利用分治的方法查找它第一次出现的位置。

示例：数组：1  2  3  3  3  3  3  5 ；8个元素，查找值为3的元素。

将数组分为两个子段(0+7)/2 = 3： 1  2  3  3  3  3  3  5

在查找到元素后记录该位置flag ，由于搜索的是第一次出现的位置，所以 应该搜索左子数组，调整搜索上界为mid-1，即为high=2;

在此范围内继续进行二分查找，实际上就是在查找到元素的时候并不停止搜索，而是继续搜索直到搜索子数组不存在。

<table style="line-height:18px; text-align:left; background-color:rgb(255,240,209); color:rgb(0,0,0); font-family:宋体,Arial; font-size:12px; padding:0pt; margin-left:1.7pt; border-collapse:collapse"> 
 <tbody style="line-height:21px"> 
 <tr> 
 <td colspan="2" style="line-height:1.5; padding:0pt; width:338.15pt"> 语法：result=search_bin(int&nbsp;*t,int&nbsp;k,int&nbsp;n); </td> 
 </tr> 
 <tr style="height:16.35pt"> 
 <td colspan="2" style="line-height:1.5; padding:0pt; width:338.15pt"> 参数： </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> t[]： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 待查找数组 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> k： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 查找关键字 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> n： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 数组元素个数 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 返回值： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 如果k在t[]中存在，输出i,i为k在t[]中第一次出现的位置：t[i]=k，否则输出－1 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 注意： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> &nbsp;数组元素从0开始存储 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> &nbsp; </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 要求查找数组是有序升序序列 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 源程序： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> &nbsp; </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> int&nbsp;search_bin(int&nbsp;*t,int&nbsp;k,int&nbsp;n) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;low=0,high=n-1,mid; int&nbsp;&nbsp;flag&nbsp;=&nbsp;-1; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(low&lt;=high) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mid=(low+high)/2; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(k==t[mid])&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag&nbsp;=&nbsp;mid; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;high&nbsp;=&nbsp;mid-1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//如果查找最后一次出现的位置 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//low&nbsp;=&nbsp;mid&nbsp;+&nbsp;1;; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;(k&lt;t[mid])&nbsp;high=mid-1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;low=mid+1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} if(flag&nbsp;==&nbsp;-1) &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;-1; else return&nbsp;flag; } </td> 
 </tr> 
 </tbody> 
</table>

测试程序：

\#include <stdio.h>

\#include <stdlib.h>

\#include <math.h>

int   cmp   (   const   void   \*a   ,   const   void   \*b   )

return   \*(int   \*)a   -   \*(int   \*)b;

int search\_bin(int \*t,int k,int n)\{

int low=0,high=n-1,mid;

int  flag = -1;

while (low<=high)

mid=(low+high)/2;

if (k==t\[mid\])

flag = mid;

high = mid-1;

//如果查找最后一次出现的位置

//low = mid + 1;;

else if (k<t\[mid\]) high=mid-1;

else low=mid+1;

if(flag == -1)

return -1;

else

return flag;

int main(int argc, char \*\*argv)

int array\[100\];

int i,j;

int p\[2\];

int key;

srand(time(0));

for(i = 0; i< 100; i++)

array\[i\] = rand()%100;

qsort(array,100,sizeof(array\[0\]),cmp);

for(i = 0; i< 10; i++)

for(j=0; j<10; j++)

printf(" %d ", array\[i\*10+j\]);

printf("\\n");

while(1)

printf("key : ");

scanf("%d", &key);

p\[0\] = search\_bin(array,key,100);

printf("%d \\n",p\[0\]);

return 0;

程序结果：

0  1  1  3  3  4  5  5  6  7

7  7  8  9  9  9  12  14  15  15

16  19  19  20  20  21  21  24  26  26

26  27  30  31  32  34  34  34  34  35

35  36  37  37  37  38  39  39  39  39

39  39  42  43  44  45  45  47  51  51

51  52  53  55  55  55  55  56  56  58

58  63  63  66  67  68  68  70  71  71

74  75  77  77  78  82  84  84  85  85

85  86  89  90  90  93  94  94  97  99

key : 3

key : 5

key : 9

key : 0

key : 1

key :

3.改进二分查找--若查找的元素未出现则返回出现的中间位置

在之前的二分查找中都没有考虑没有查找到关键字时返回该关键字应该位于数组哪个位置的情况，而是直接考虑的是返回失败，二分查找是在查找的时候是利用的是中间位置与关键值的大小比较，当查找失败的时候，查找到得位置也就当前最接近关键值的位置，且这样找到的关键值的位置是第一场出现的位置。我们可以利用这个特性来查找到关键值的位置。我们还是用一个例子来说明该种情况：

示例：如有已排序数组有8个元素如下查找元素x = 3;

1  5  6  7  9  10  12  44

将数组分为两个子段(0+7)/2 = 3： 1  5  6  7  9  10  12  44

Array\[3\] = 7 > x=3，继续查找，high = mid -1; mid = 1;

此时array\[1\] = 5 > x = 5,继续查找, high = mid-1; mid = 0;

此时array\[0\] = 1 < x = 5，继续查找 high = 0, low = 1，失败退出，此时mid = 0，为最接近关键值的值，通过比较可以得出。

<table style="line-height:18px; text-align:left; background-color:rgb(255,240,209); color:rgb(0,0,0); font-family:宋体,Arial; font-size:12px; padding:0pt; margin-left:1.7pt; border-collapse:collapse"> 
 <tbody style="line-height:21px"> 
 <tr> 
 <td colspan="2" style="line-height:1.5; padding:0pt; width:338.15pt"> 语法：void&nbsp;search_bin(int&nbsp;*t,int&nbsp;k,int&nbsp;n,&nbsp;int&nbsp;p[2]); </td> 
 </tr> 
 <tr style="height:16.35pt"> 
 <td colspan="2" style="line-height:1.5; padding:0pt; width:338.15pt"> 参数： </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> t[]： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 待查找数组 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> k： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 查找关键字 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> n： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 数组元素个数 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> int&nbsp;p[2] </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> p[0]代表关键值下界，p[1]代表关键值上界 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 返回值： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 无 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 注意： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> &nbsp;数组元素从0开始存储 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> &nbsp; </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> 要求查找数组是有序升序序列 </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> 源程序： </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="line-height:1.5; padding:0pt; width:44.8pt"> &nbsp; </td> 
 <td style="line-height:1.5; padding:0pt; width:293.35pt"> void&nbsp;search_bin(int&nbsp;*t,int&nbsp;k,int&nbsp;n,&nbsp;int&nbsp;p[2]) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;low=0,high=n-1,mid; int&nbsp;&nbsp;flag&nbsp;=&nbsp;-1; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(low&lt;=high) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mid=(low+high)/2; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(k==t[mid])&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag&nbsp;=&nbsp;mid; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;(k&lt;t[mid])&nbsp;high=mid-1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;low=mid+1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} if(flag&nbsp;==&nbsp;-1) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;if(t[mid]&nbsp;&gt;&nbsp;k) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[0]&nbsp;=&nbsp;mid-1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[1]&nbsp;=&nbsp;mid;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[0]&nbsp;=&nbsp;mid; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[1]&nbsp;=&nbsp;mid+1;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} } else { &nbsp;&nbsp;&nbsp;&nbsp;p[0]&nbsp;=&nbsp;p[1]&nbsp;=&nbsp;flag&nbsp;;&nbsp; } } </td> 
 </tr> 
 </tbody> 
</table>