今天看編程之美，3.11里面有個改錯題，是針對一個二分查找算法的糾錯，先說下題目：找出一個有序（字典序）字符串數組arr中值等于字符串v的元素的序號，如果有多個元素滿足條件，則返回其中序號最大的。
要說算法這個問題確實不難，但是寫程序的話需要注意一些地方，書中已經寫的比較完美了，就不貼了，這里貼一個通用版本，也是模仿斯坦福公開課《編程范式》中講解的來寫的，這個bisearch()和c庫中的bsearch()很像。
1 int bisearch(const void *arr,
2 const void *elem,
3 int elem_size,
4 int elem_num,
5 int (*fcmp)(const void *, const void *)) {
6 int low = 0;
7 int high = elem_num - 1;
8 int mid;
9
10 while (low < high - 1) {
11 mid = ((high - low) >> 1) + low;
12 int status =
13 fcmp((const void *)((char *)arr + mid * elem_size),
14 (const void *)elem);
15 if (status <= 0) {
16 low = mid;
17 } else {
18 high = mid;
19 }
20 }
21
22 if (fcmp((const void *)((char *)arr + high * elem_size),
23 (const void *)elem) == 0) {
24 return high;
25 } else if (fcmp((const void *)((char *)arr + low * elem_size),
26 (const void *)elem) == 0) {
27 return low;
28 } else {
29 return -1;
30 }
31 }
32
可以看到如果題目變一下，那么上面的函數也需要改變，比如，如果有多個元素滿足這個條件，則返回最小的序號，那么程序修改如下：
int bisearch(const void *arr,
const void *elem,
int elem_size,
int elem_num,
int (*fcmp)(const void *, const void *)) {
int low = 0;
int high = elem_num - 1;
int mid;
while (low < high - 1) {
mid = ((high - low) >> 1) + low;
int status =
fcmp((const void *)((char *)arr + mid * elem_size),
(const void *)elem);
if (status >= 0) {
high = mid;
} else {
low = mid;
}
}
if (fcmp((const void *)((char *)arr + low * elem_size),
(const void *)elem) == 0) {
return low;
} else if (fcmp((const void *)((char *)arr + high * elem_size),
(const void *)elem) == 0) {
return high;
} else {
return -1;
}
}
其實也就是修改一下比較的順序。
如果要求大于v的最小的數組元素的序號i呢？我們依然先求等于v的最大的序號j，不過在確定low和high之后，需要如下考慮：
若arr[low] > v，那么我們可以肯定low即為i
若arr[high] < v，那么我們也可以肯定沒有比v大的元素，返回-1
若arr[high] == v，那么如果high = elem_num - 1，則說明數組中所有元素都小于等于v，則返回-1，否則返回high + 1
否則返回high
程序如下：
1 int bisearch(const void *arr,
2 const void *elem,
3 int elem_size,
4 int elem_num,
5 int (*fcmp)(const void *, const void *)) {
6 int low = 0;
7 int high = elem_num - 1;
8 int mid;
9
10 while (low < high - 1) {
11 mid = ((high - low) >> 1) + low;
12 int status =
13 fcmp((const void *)((char *)arr + mid * elem_size),
14 (const void *)elem);
15 if (status <= 0) {
16 low = mid;
17 } else {
18 high = mid;
19 }
20 }
21
22 int stlow =
23 fcmp((const void *)((char *)arr + low * elem_size),
24 (const void *)elem);
25 int sthigh =
26 fcmp((const void *)((char *)arr + high * elem_size),
27 (const void *)elem);
28 if (stlow > 0) {
29 return low;
30 } else if (sthigh < 0) {
31 return -1;
32 } else if (sthigh == 0) {
33 if (high == elem_num - 1) {
34 return -1;
35 } else {
36 return high + 1;
37 }
38 }
39 return high;
40 }
如果要求小于v的最大的數組元素的序號i呢？我們依然先求等于v的最小的序號j，不過在確定low和high之后，需要如下考慮：
若arr[low] > v，那么我們可以肯定沒有比v大的元素，返回-1
若arr[high] < v，那么返回high
若arr[low] == v，那么如果low = 0，則說明數組中所有元素都大于等于v，則返回-1，否則返回low - 1
否則返回low
程序如下：
1 int bisearch(const void *arr,
2 const void *elem,
3 int elem_size,
4 int elem_num,
5 int (*fcmp)(const void *, const void *)) {
6 int low = 0;
7 int high = elem_num - 1;
8 int mid;
9
10 while (low < high - 1) {
11 mid = ((high - low) >> 1) + low;
12 int status =
13 fcmp((const void *)((char *)arr + mid * elem_size),
14 (const void *)elem);
15 if (status >= 0) {
16 high = mid;
17 } else {
18 low = mid;
19 }
20 }
21
22 int stlow =
23 fcmp((const void *)((char *)arr + low * elem_size),
24 (const void *)elem);
25 int sthigh =
26 fcmp((const void *)((char *)arr + high * elem_size),
27 (const void *)elem);
28 if (stlow > 0) {
29 return -1;
30 } else if (sthigh < 0) {
31 return high;
32 } else if (stlow == 0) {
33 if (low == 0) {
34 return -1;
35 } else {
36 return low - 1;
37 }
38 }
39 return low;
40 }
posted on 2012-09-02 18:37
myjfm 閱讀(514)
評論(1) 編輯 收藏 引用 所屬分類:
算法基礎