算法练习(63): 修改二分查找算法(1.4.10)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 二分查找

题目

1.4.10 修改二分查找算法，使之总是返回和被查找的键匹配的索引最小的元素。（且仍能够保证对数级别的运行时间）

---

1.4.10 Modify binary search so that it always returns the element with the smallest index that matches the search element (and still guarantees logarithmic running time).

分析

稍加思考，我们不难写出如下代码

public int rank(int key, int[] a) { // 数组必须是有序的
      int lo = 0;
      int hi = a.length - 1;
      while (lo <= hi) { // 被查找的键要么不存在，要么必然存在于a[lo..hi]之中
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid])
                  hi = mid - 1;
            else if (key > a[mid])
                  lo = mid + 1;
            else{
                  // 先向左边查找，但要注意避免越界
                  int minIndex = mid;
                  while (a[minIndex] == key) {
                        --minIndex;
                        if (minIndex < 0) {
                              break;
                        }
                  }
                  return minIndex+1;
            }

      }           

      return -1;
}

并且我们可以写个测试用例

int[] b = { 1, 2, 3, 5, 4, 5, 6, 77, 7, 8, 8, 9, 1, 11, 22, 234, 90 };
Arrays.sort(b);
BinarySearch search = new BinarySearch();

int targetKey = 1;
int index = search.rank(targetKey,b);
System.out.println(targetKey + "在第"+index+"个");

这里顺便列举网上的一些错误的方式，例如

else {
    while(mid>0&&a[--mid]==key);  //该语句排除了左边与之相同的值
    return mid+1;
}

这一段明显是有问题的，本测试用例就可以反驳，当targetKey为1的时候，错误的方式算出来的是1，其实是0。

接下来我们接着分析。

上面我们的解法是不是对的呢，只能说大部分情况下没问题，但这里给出一个极端的情况

int[] b = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };

这里，时间复杂度就不是对数了，我们需要重新考虑解决方案。
这里有个很简洁的解决方案：find lowest index of a given value in a presorted array 大家可以看看，笔者的答案就是基于这个解法的。

大概的思路就是，原来的if (a[mid] < key)和else if (a[mid] > key)不变，而是变if (a[mid] == key)。当if (a[mid] < key)满足后，再去看它前面的一个元素是否也满足，即a[mid-1] == key，当然，为了避免越界，我们要先加mid > 0的判断。

答案

public int rank(int[] a, int key) {
      int hi = a.length;
      int lo = 0;
      int mid = 0;
      while(lo < hi){
            mid = (hi + lo) / 2;
            if (a[mid] < key) {
            lo = mid + 1;
            }else if (a[mid] > key) {
            hi = mid;
            }else if (mid > 0 && a[mid-1] == key) {
            hi = mid;
            }else {
                  return mid;
            }
      }
      
      return -1;
}

代码索引

BinarySearch_ON.java

BinarySearch_OlogN.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。