二分查找作为高效的查找算法,可以说是每个学计算机的都应该懂的,在每年的面试中,可以说是必须考察的点;
其实我们小时候就用过这个算法,只是没注意罢了,比如一本书300页,你要找第100页,你翻到了第20页,那么你肯定向后翻,你又翻到了第80页,你肯定继续向后找,每次砍掉一些。还比如英语字典,是按照单词的字典序排列的,你也是利用上面的算法在找。其实这就是二分查找。
有序的线性表(一定得是数组存储的,由于需要快速取得对应位置的值)
1 |
int binarySearch( int
arr[], int
beg, int
end, int
target) |
1、安全性检测
assert(beg >= 0 && beg <= end && end < sizeof(arr)/sizeof(int)); /*sizeof这个语法貌似不一定对*/
1
2 |
if (beg == end && beg == 0) return
-1; |
1
2
3 |
/*method1:*/
int mid = (beg + end) / 2; /*method2:*/
int mid = beg + (end - beg) /2 ; /*method3:*/
int mid = beg + ((end - beg) >> 1); |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
int findEqual( int
arr[], int
beg, int
end, int
target) { assert (0 <= beg && beg <= end); int
mid = -1; int
ret = -1; while
(beg <= end) { mid = beg + ((end - beg)>>1); if
(arr[mid] == target) { ret = mid; break ; } else
if (arr[mid] > target){ end = mid - 1; } else
{ beg = mid + 1; } } return
ret; } |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 |
int findMinEqual( int
arr[], int
beg, int
end, int
target) { assert (0 <= beg && beg <= end); int
mid = -1; int
ret = -1; while
(beg <= end) { mid = beg + ((end - beg)>>1); if
(arr[mid] == target) { if
(mid - 1 >= 0 && arr[mid - 1] == target) end = mid - 1; else { ret = mid; break ; } } else
if (arr[mid] > target){ end = mid - 1; } else
{ beg = mid + 1; } } return
ret; } |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 |
int findMaxEqual( int
arr[], int
beg, int
end, int
target) { assert (0 <= beg && beg <= end); int
mid = -1; int
ret = -1; while
(beg <= end) { mid = beg + ((end - beg)>>1); if
(arr[mid] == target) { if
(mid + 1 <= end && arr[mid + 1] == target) { beg = mid + 1; } else { ret = mid; break ; } } else
if (arr[mid] > target){ end = mid - 1; } else
{ beg = mid + 1; } } return
ret; } |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 |
int findMaxLess( int
arr[], int
beg, int
end, int
target) { assert (0 <= beg && beg <= end); int
mid = -1; while
(beg + 1 < end) { mid = beg + ((end - beg)>>1); if
(arr[mid] >= target) { end = mid - 1; } else { beg = mid; } } if
(arr[end] < target) return
end; else
if (arr[beg] < target) return
beg; else return
-1; } |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 |
int findMinGreat( int
arr[], int
beg, int
end, int
target) { assert (0 <= beg && beg <= end); int
mid = -1; while
(beg + 1 < end) { mid = beg + ((end - beg)>>1); if
(arr[mid] <= target) beg = mid + 1; else end = mid; } if
(arr[beg] > target) return
beg; else
if (arr[end] > target) return
end; else return
-1; } /*别人的写法*/ int
findOther( int
arr[], int
beg, int
end, int
target) { int
mid = -1; while
(beg <= end) { mid = beg + (end - beg) / 2; if
(arr[mid] <= target) beg = mid + 1; else end = mid - 1; } if
(arr[beg] <= target) return
-1; else return
beg; } |
引用貌似得翻墙
由于水平有限,若发现错误请告知,共同进步;
1、二分查找(Binary
Search)需要注意的问题,以及在数据库内核中的实现
2、编程之美p261页
字符串专题,欢迎继续支持
原文:http://www.cnblogs.com/Cunch/p/3594445.html