bobo老师,你好,请问哪里有二分查找相关的变式题和解答呢?

Question

比如,这两类变式问题:

1. 带有重复元素的查找. 查询重复元素的上界或下界.
2. 查找<=target或<target的集合中的最后一个元素.

这2类变式题应该都可以通过改变判断分支的条件来做。
但是具体去分析时,要知道修改哪个判断分支以及怎么修改,我分析得不是很顺畅,经常都不能做出最简便的修改方式,往往会绕一下子.

Answer 1

liuyubobobo 2019-12-25 17:01:34

你的这两个需求，其实都可以被我提供的这个补充代码中的两个算法：floor 和 ceil 所涵盖。仔细梳理一下这个代码，看看能不能理解？

传送门（C++）：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-02-Floor-and-Ceil-in-Binary-Search/main.cpp

继续加油！：）

• 提问者 agjsytt #1

  谢谢bobo老师
  我发现floor和"<=target的最后一个元素"这2个需求还是有点区别.
  * 比如,存在重复target的情况.
  如果找到target, floor返回第一个target的索引,另外一个需求却是要求返回最后一个target的索引.
  
  第二个需求的最简洁代码如下:
  ```
  int searchLastEqualOrSmaller(int *arr, int n, int key)
  {
      int left=0, right=n-1;
      while(left<=right) {
          int m = (left+right)/2;
          if(arr[m] > key) right = m-1;
          else if (arr[m] <= key) left = m+1;
      }
      return right;
  }
  ```
  对比searchLastEqualOrSmaller和floor的代码, 我发现floor代码还是比较复杂的,比如 "向上取整避免死循环" 和 最后返回时的判断. 我看完代码能勉强能理解,但是我似乎说不清楚为啥这么写.

• liuyubobobo 回复 提问者 agjsytt #2

  <=target的最后一个元素 是不是就是 ceil(target)？

• 提问者 agjsytt 回复 liuyubobobo #3

  好滴,谢谢bobo老师