二分查找作为高效的查找算法，可以说是每个学计算机的都应该懂的，在每年的面试中，可以说是必须考察的点；
其实我们小时候就用过这个算法，只是没注意罢了，比如一本书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