Binary Search 面试最常考题（下）

昨天我们说了如何用 binary search 在 rotate array 中找它的最小值的两道题，今天来看一下如何找一个 target 值。

先来看 Leetcode 33 题：

这题有多种解法，下面讲的是我觉得最好懂也是面试时最好讲的。

一个 array rotate 之后，其实是两段分别 sorted 的 array。那么从中间分开，必然至少有一半是 sorted 的，另一半是 rotate 的，所以：

1. 先判断这边是不是 sorted 的：array[left] <= array[mid]，必须写等号，因为mid可能等于left
2. 在 sorted 的那边，判断 target 是否在这个区间内，相应的移动左右指针

注意⚠️：这里 while 循环的条件最好包含等于，因为当 left==right 的时候也就是只剩下一个元素的时候也是可以进去判断的，这样跳出循环就说明没有这个 target 了。

如果不写等于号，那就需要跳出循环再判断一下，多此一举。

easy way to find the condition: {1}, target = 1.

// return index
class Solution {
  public int search(int[] nums, int target) {
    if(nums == null || nums.length == 0) {
      return -1;
    }
    int left = 0;
    int right = nums.length - 1;
    while(left <= right) { 
      int mid = left + (right - left)/2;
      if(nums[mid] == target) {
        return mid;
      }
      if(nums[left] <= nums[mid]) { // left part is sorted
        if(target >= nums[left] && target <= nums[mid]) { // target is in the left part
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else { // right part is sorted
        if(target >= nums[mid] && target <= nums[right]) { // target is in the right part
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    return -1; // does not find
  }
}

Follow up 也很自然的能想到，就是 array may contain duplicates 的情况。这个就不返回具体的 index 了，只需要返回 boolean 就行。

那和昨天的第二题一样，如果 nums[mid] == nums[left]，无法判断sorted

那如果判断 nums[mid] == nums[right] 呢？[1, 1, 3, 1], 3.

也就是当 nums[mid] == nums[left/right] 时，无法判断target在哪边，所以无论和左右哪个端点值相比较，只要相等了，就只能一步步走。

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left)/2;
            if(nums[mid] == target) {
                return true;
            }
            if(nums[mid] == nums[right]) { // mid不是target，所以right也不是
                right--;
            } else if(nums[mid] < nums[right]) {
                if(target >= nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if(target >= nums[left] && target <= nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return false;
    }
}

题目就到这里了，感谢你的阅读~ 

欢迎扫下图二维码关注此公众号或者添加我个人微信号 nycsde7。

文末彩蛋时间～

这个周末做了牛尾的两种做法，都还不错！

买回来的是生肉，我习惯于先做肉本身。首先是把牛尾焯水，然后用高压锅做好了，这样就能放起来每顿吃饭的时候加些配菜，很快就能做好。

昨天是加了白菜乱炖。。味道嘛。。只能说比较朴素，全靠牛尾撑着！

今天做了传统的西红柿牛尾，不过加了 cream 和 Basil，使之味道更丰富：首先是 herb 的香味，然后就是西红柿的酸味，还有一点海鲜菇的鲜味，最后留下 cream 的奶香味，非常有层次。

今天就这些了，我们明天见~