今天看编程之美，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 阅读(505)
评论(1) 编辑 收藏 引用 所属分类:
算法基础