2013-01-27 循环有序数组的二分查找

1
/*
2
p is the start index,
3
q is the end index,
4
x is the target data
5
*/
6
int binary_search(int x, int p, int q, int *a) {
7
if (p >= q && a[p] != x)
8
return -1;
9
10
int m = (p + q) / 2;
11
12
if (a[m] == x)
13
return m;
14
15
if (x > a[m])
16
p = m + 1;
17
else
18
q = m - 1;
19
20
return binary_search(x, p, q, a);
21
}
Copied!

1
search: 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
2
----------------------------------------------------------------------------------------------------
3
p= 0, m= 9, q=19 | 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8,
Copied!

1
search : 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
2
----------------------------------------------------------------------------------------------------
3
p= 0, m= 9, q=19 | 9, 10, 11, 12, 13, 14, 15, 16, 18, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8,
4
p=10, m=14, q=19 | 19, 0, 1, 2, 3, 4, 5, 6, 7, 8,
5
p=10, m=11, q=13 | 19, 0, 1, 2,
6
result: 11
Copied!

1.
如何判断一段数组是单调递增呢？在该段数组的头、中间、尾三个位置p,m,q取三个值a[p], a[m], a[q]，如果是单调递增则一定满足 a[p] >= a[m] >= a[q]，否则则非单调递增。
2.
判断目标元素下一步所在区间，有几种情况：
当 x > a[m] 时，
右半边是单调递增区间，并且x在此区间内，下一步则可在此右半边区间内查找
右半边是单调递增区间，并且x不在此区间内，下一步在左半边查找
右半边是非单调递增区间，则x必然在此区间内，下一步在右半边查找
当 x < a[m] 时， 同理类似
左半边是单调递增区间，并且x在此区间内，下一步则可在此左半边区间内查找
左半边是单调递增区间，并且x不在此区间内，下一步在右半边查找
左半边是非单调递增区间，则x必然在此区间内，下一步在左半边查找
3.
判断是否在单调递增部分，只需与区间的另外一头的元素比较一下大小即可知道

1
#include <stdio.h>
2
3
#define N 20
4
int arr[N] = {9,10,11,12,13,14,15,16,17,18,19,0,1,2,3,4,5,6,7,8};
5
6
7
printf("search :%2d %*c | ", target, 5, ' ');
8
for (int i = 0; i < N; i++) {
9
printf("%2d ", i);
10
}
11
printf("\n");
12
for (int i = 0; i< N; i++) {
13
printf("-----");
14
}
15
printf("\n");
16
}
17
18
void print_array(int p, int m, int q, int *a) {
19
printf("p=%2d, m=%2d, q=%2d |%*c", p, m, q, 4 * p + (p>0?1:0), ' ');
20
for (int i = p; i <= q; i++) {
21
printf("%2d, ", a[i]);
22
}
23
printf("\n");
24
}
25
26
/* 非递归方式 */
27
int search_loop_array(int x, int* a, int length) {
28
int p = 0;
29
int q = length - 1;
30
31
while ( p <= q ) {
32
int m = ( p + q ) / 2;
33
34
print_array(p, m, q, a);
35
36
if ( x == a[m] )
37
return m;
38
39
if ( x > a[m] ) {
40
int mm = ( m + q ) / 2;
41
int increase = (a[m] <= a[mm] && a[mm] <= a[q]);
42
if ( ( increase && x <= a[q] ) || ! increase)
43
p = m + 1;
44
else
45
q = m - 1;
46
} else {
47
int mm = ( p + m ) / 2;
48
int increase = a[p] <= a[mm] && a[mm] <= a[m];
49
if ( increase && x >= a[p] || !increase)
50
q = m - 1;
51
else
52
p = m + 1;
53
}
54
}
55
56
return -1;
57
}
58
59
/* 递归方式 */
60
int search_loop_array2(int x, int low, int high, int* a) {
61
if (low >= high && a[low] != x)
62
return -1;
63
64
int m = (low + high) / 2;
65
66
print_array(low, m, high, a);
67
68
if ( x == a[m] )
69
return m;
70
71
if ( x > a[m] ) {
72
int mm = (m + high) / 2;
73
int increase = (a[m] <= a[mm] && a[mm] <= a[high]);
74
75
if ( !increase || (increase && x <= a[high] ) )
76
low = m + 1;
77
else
78
high = m - 1;
79
80
} else {
81
int mm = (low + m) / 2;
82
int increase = (a[low] <= a[mm] && a[mm] <= a[m]);
83
84
if ( !increase || (increase && x >= a[low] ) )
85
high = m - 1;
86
else
87
low = m + 1;
88
}
89
90
return search_loop_array2(x, low, high, a);
91
}
92
93
int main() {
94
95
for (int i = 0; i < N; i++) {
96
97
98
// printf("result: %d\n\n", search_loop_array(i, arr, N));
99
printf("result: %d\n\n", search_loop_array2(i, 0, N-1, arr));
100
}
101
return 0;
102
}
Copied!