二分（折半）查找算法 收藏

编程技术  /  houtizong 发布于 3年前   115

折半查找法是对有序数组进行查找的高效算法，本文主要对一些边界情况做一些分析，结合《编程之美》上的讨论，给出实际的代码。

基本的折半查找的代码如下：（假设数组有序且没有重复元素）

view plaincopy to clipboardprint?
int bin_search(char *s,char v,int n)
{
int max = n-1,min = 0,mid = 0;
while(min<=max)
{
mid = min+(max-min)/2;//防止加法溢出
if(s[mid]<v) min = mid + 1;
else if(s[mid]>v) max = mid - 1;
else return mid;
}
return -1;
}
int bin_search(char *s,char v,int n)
{
int max = n-1,min = 0,mid = 0;
while(min<=max)
{
mid = min+(max-min)/2;//防止加法溢出
if(s[mid]<v) min = mid + 1;
else if(s[mid]>v) max = mid - 1;
else return mid;
}
return -1;
}

但是当有序数组中有重复元素时，就需要考虑特殊情况：

1，找到数组中等于v的元素的最大序号。实现如下：

对于退出条件：min<max && min+1 != max，而不是上述的min<=max，是为了保证循环的正常退出。

因为上述中每次循环min或者max都会改变，能够保证循环的正常退出，而这里当s[mid]<=v时，min的值不变，可能出现无限循环的情况。

例如，对于数组a[]={2}，寻找2最后一次次出现情况时，第一次循环,min=0，min=0,max=0，满足s[mid]<=v条件，此时min=mid=max=0，如果循环退出条件仍然是min<=max，则会出现无限循环。

view plaincopy to clipboardprint?
int bin_search1(char *s,char v,int n)
14 {
15 int min = 0,max = n-1,mid = 0;
16 while(min < max && min+1 != max)
17 {
18 mid = min+(max-min)/2;//防止加法溢出
19 if(s[mid] <= v)
20 {
21 min = mid;
22 }
23 else
24 {
25 max = mid - 1;
26 }
27 }
28 if(s[max] == v)
29 {
30 return max;
31 }
32 else if(s[min] == v)
33 {
34 return min;
35 }
36 else if(min + 1 == max)
37 {
38 return -1;
39 }
40 }
int bin_search1(char *s,char v,int n)
14 {
15 int min = 0,max = n-1,mid = 0;
16 while(min < max && min+1 != max)
17 {
18 mid = min+(max-min)/2;//防止加法溢出
19 if(s[mid] <= v)
20 {
21 min = mid;
22 }
23 else
24 {
25 max = mid - 1;
26 }
27 }
28 if(s[max] == v)
29 {
30 return max;
31 }
32 else if(s[min] == v)
33 {
34 return min;
35 }
36 else if(min + 1 == max)
37 {
38 return -1;
39 }
40 }

2，找到数组中等于v的元素的最小序号。实现如下：

view plaincopy to clipboardprint?
int bin_search2(char *s,char v,int n)
42 {
43 int min = 0,max = n-1,mid = 0;
44 while(min < max && min+1 != max)
45 {
46 mid = min + (max - min)/2;
47 if(s[mid] >= v)
48 {
49 max = mid;
50 }
51 else
52 {
53 min = mid + 1;
54 }
55 }
56 if(s[min] == v)
57 {
58 return min;
59 }
60 else if(s[max] == v)
61 {
62 return max;
63 }
64 else if(min + 1 == max)
65 {
66 return -1;
67 }
68 }
int bin_search2(char *s,char v,int n)
42 {
43 int min = 0,max = n-1,mid = 0;
44 while(min < max && min+1 != max)
45 {
46 mid = min + (max - min)/2;
47 if(s[mid] >= v)
48 {
49 max = mid;
50 }
51 else
52 {
53 min = mid + 1;
54 }
55 }
56 if(s[min] == v)
57 {
58 return min;
59 }
60 else if(s[max] == v)
61 {
62 return max;
63 }
64 else if(min + 1 == max)
65 {
66 return -1;
67 }
68 }

3，找到数组中小于v的元素的最大序号。实现如下：首先根据1，找到等于v的最小序号，然后-1（如果合法）。

4，找到数组中大于v的元素的最小序号。实现如下：首先根据2，找到等于v的最大序号，然后+1（如果合法）。

在这几种情况中，关键点是“结束循环的边界条件”。

想到的测试例子如下：

s="abbcdef" 奇数个

s="abbcdf"偶数个

s="aaaaaaa" 奇数个

s="a"一个

s="aaaaaa"偶数个

s="abbbbb"

s="aaaab"