二分查找

• 来源说明
• 704. Binary Search
  • 思路
  • C++ 写法
    • 二分查找第一种写法
    • 二分查找第二种写法
  • 总结
• 35. Search Insert Position
  • 思路
  • C++ 解法
  • Java 解法
  • Python 解法
• 34. Find First and Last Position of Element in Sorted Array
  • 思路
  • C++ 解法1
  • C++ 解法2
  • Java 解法
  • Python 解法
• 162. Find Peak Element
  • 思路
  • C++ 解法
  • Java 解法
  • Python 解法

来源说明

二分查找来源于编程随想录

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 < nums[i], target < 10^4
• All the integers in nums are unique.
• nums is sorted in ascending order.

思路

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

下面我用这两种区间的定义分别讲解两种不同的二分查找写法。

C++ 写法

二分查找第一种写法

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

代码如下：

// 版本一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

二分查找第二种写法

如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

有如下两点：

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
• if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

代码如下：（详细注释）

// 版本二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

总结

二分法是非常重要的基础算法，为什么很多同学对于二分法都是一看就会，一写就废？

其实主要就是对区间的定义没有理解清楚，在循环中没有始终坚持根据查找区间的定义来做边界处理。

区间的定义就是不变量，那么在循环中坚持根据查找区间的定义来做边界处理，就是循环不变量规则。

本篇根据两种常见的区间定义，给出了两种二分法的写法，每一个边界为什么这么处理，都根据区间的定义做了详细介绍。

相信看完本篇应该对二分法有更深刻的理解了。

35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

思路

先看在不在数组里，在的话输出下标；不在的话看是不是比前一个大，比后一个小，注意数组越界的问题。

要是上来就比第一个数小就输出零，比最后一个大输出数组长度。

不管 target 是在一个左闭右闭的区间里还在在一个左闭右开的区间里，在数组中找不到 target 时，都需要return left。

C++ 解法

假设target 是在一个在左闭右闭的区间里，也就是[left, right]

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            int mid = (right + left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return left;

    }
};

Java 解法

假设target 是在一个在左闭右闭的区间里，也就是[left, right]

class Solution {
    public int searchInsert(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){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return left;
    }
}

Python 解法

假设target 是在一个在左闭右闭的区间里，也就是[left, right]

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        
        return left

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

思路

寻找target在数组里的左右边界，有如下三种情况：

• 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
• 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
• 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

这三种情况都考虑到，说明就想的很清楚了。

接下来，在去寻找左边界，和右边界了。

方法1：一次二分查找，再扩展区间

方法2：使用两次二分查找，分别查找lower_bound和upper_bound。

刚刚接触二分搜索的同学不建议上来就想用一个二分来查找左右边界，很容易把自己绕进去，建议扎扎实实的写两个二分分别找左边界和右边界

确定好：计算出来的右边界是不包含target的右边界，左边界同理。

C++ 解法1

假设target 是在一个在左闭右闭的区间里，也就是[left, right]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
};

C++ 解法2

lower_bound倾向于找左边的元素，所以只有nums[mid] < target时才移动左指针；而upper_bound倾向于找右边的元素，所以当nums[mid] <= target就向右移动左指针了。

lower_bound返回的是开始的第一个满足条件的位置，而upper_bound返回的是第一个不满足条件的位置。所以，当两个相等的时候代表没有找到，如果找到了的话，需要返回的是[left, right - 1]。

class Solution {
public:
    int lower_bound(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while(left < right){
            int mid = (right + left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;

    }

    int upper_bound(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size();
        while(left < right){
            int mid = (right + left) / 2;
            if(nums[mid] <= target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;

    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = lower_bound(nums, target);
        int rightBorder = upper_bound(nums, target);

        if (leftBorder == rightBorder) 
            return {-1, -1};
        else
            return {leftBorder, rightBorder - 1};
    }
};

Java 解法

假设target 是在一个在左闭右开的区间里，也就是[left, right)

先尝试找到一个target，找不到则返回{-1, -1}，找到时则向两边扩展得结果

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int left = 0;
        int right = nums.length;
        boolean isExist = false;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                isExist = true;
                break;
            }
        }
        if(isExist){
            int mid = left + (right - left) / 2;
            int i = mid;
            int j = mid;
            while(i >= 0 && nums[i] == target){
                i--;
            }
            while(j < nums.length && nums[j] == target){
                j++;
            }
            result[0] = i + 1;
            result[1] = j - 1;
        }
         return result;
    }
}

Python 解法

假设target 是在一个在左闭右开的区间里，也就是[left, right)

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = bisect.bisect_left(nums, target)
        right = bisect.bisect_right(nums, target)
        if left == right:
            return [-1, -1]
        return [left, right - 1]

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i + 1] for all valid i.

思路

给一个数组，找出其中的峰顶数据，就是大于两个邻居的数的index，如果有多个答案，任意一个都可以。

这个题可以直接使用最简单的暴力搜索，遍历整个数组，时间复杂度为O(n).虽然题目要求是log时间，但是这样也可以AC。

但是也可以实现O(logn)的时间复杂度。可以用binary search。每次寻找中间的数，如果恰好是峰顶数据，就返回index。如果不是，就查看其与中间元素相邻的左边和右边的值，选取大于中间元素的那边的一半数组继续遍历，如果两边都大于，就随便选一个。注意，这里是没有考虑相同的数据挨着的情况的。

C++ 解法

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int size = nums.size();
        if(size <= 1 || nums[0] > nums[1])
            return 0;
        if(nums[size - 2] < nums[size - 1]){
            return size - 1;
        }
        for(int i = 1; i < nums.size() - 1; i++){
            if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]){
                return i;
            }
        }
        return -1;
    }
};

Java 解法

分治策略

二分查找区间类型为左闭右闭

class Solution {
    public int findPeakElement(int[] nums) {
        return binarySearchToFindPeakElement(nums, 0, nums.length - 1);
    }
    public int binarySearchToFindPeakElement(int[] nums, int left, int right){
        if(left > right)
            return -1;
        if(left == right)
            return left;
        if(left + 1 == right) 
            return nums[left] > nums[right] ? left : right;
        int mid = left + (right - left) / 2;
        if(nums[mid] < nums[mid + 1]){
            return binarySearchToFindPeakElement(nums, mid + 1, right);
        }else if(nums[mid] < nums[mid - 1] ){
            return binarySearchToFindPeakElement(nums, left, mid -1);
        }else{
            return mid;
        }
    }
}

Python 解法

二分查找区间类型为左闭右闭

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right)  >> 1
            if nums[mid - 1] <= nums[mid] >= nums[mid + 1]:
                return mid
            elif nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left
        

更精简的写法如下：

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return right

最后返回right或left均可。

注意：这里和C++写法存在较大差异。