随笔-80  评论-24  文章-0  trackbacks-0
今天看编程之美,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 阅读(492) 评论(1)  编辑 收藏 引用 所属分类: 算法基础

评论:
# re: 二分查找剖析 2013-04-07 13:05 | jq
最后一例:要求小于v的最大的数组元素的序号i
最后的判断似乎不够简洁,想探讨一下,盼赐教,多谢

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;

感觉可以优化为下列:
if(sthigh<0) {
return high;
} else if(stlow<0) {
return low;
}
else {
return -1;
}
因为36行永远不会执行到:
若stlow==0, 则low == 0
反正法: 若 low>0且stlow==0, 因为刚开始low=0, 所以必定在while循环中被改变:
而low被修改的前提条件: arr[mid]< elem , 所以被改后 low=mid, arr[low]<element==>stlow!=0
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理