二分查找

基础

基本写法(元素没有重复)

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

// 递归写法
int binarySearchRecur(vector<int> &A, int target, int left, int right) {
    if (left > right) { return -1; }
    int mid = left + (right - left)/2;
    if (A[mid] > target) {
        return binarySearchRecur(A, target, left, mid-1);
    } else if (A[mid] < target) {
        return binarySearchRecur(A, target, mid + 1, right);
    } else {
        return mid;
    }
}

复制代码

查找左边界

寻找元素第一次出现的位置。

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

寻找左侧边界，小于目标元素

int binarySearchLeftBound(vector<int> &A, int target) {
    // [left, right]
    int left = 0, right = (int)A.size() - 1;
    while (left <= right) {
        int mid = left + (right - left)/2;
        if (A[mid] == target) {
            right = mid - 1;
        } else if (A[mid] > target) {
            right = mid - 1;
        } else if (A[mid] < target) {
            left = mid + 1;
        }
    }
    return left - 1;
}
复制代码

查找右边界

寻找元素最后一次出现的位置

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

寻找右侧边界，大于目标元素

int binarySearchRightBound(vector<int> &A, int target) {
    // [left, right]
    int left = 0, right = (int)A.size() - 1;
    while (left <= right) {
        int mid = left + (right - left)/2;
        if (A[mid] == target) {
            //[mid, right]
            left = mid + 1;
        } else if (A[mid] > target) {
            right = mid - 1;
        } else if (A[mid] < target) {
            left = mid + 1;
        }
    }
    return left;
}
复制代码

LeetCode 题型

easy 题型

704. 二分查找

374. 猜数字大小

278. 第一个错误的版本

medium 题型

34. 在排序数组中查找元素的第一个和最后一个位置(查找目标值的左右边界)

最直接的想法是先找左边界，在找右边界：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = searchLeftBound(nums, target);
        int right = searchRightBound(nums, target);
        vector<int> v;
        v.push_back(left);v.push_back(right);
        return v;
    }

    int searchLeftBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(target == nums[mid]) {
                right = mid - 1;
            } else if(target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if(left < nums.size() && nums[left] == target) {
            return left;
        } 
        return -1;
    }
    int searchRightBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(target == nums[mid]) {
                left = mid + 1;
            } else if(target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if(right >= 0 && nums[right] == target) {
            return right;
        }
        return -1;
    }
};
复制代码

658. 找到 K 个最接近的元素(题目有点绕)

旋转问题

33. 搜索旋转排序数组(没有重复元素，找目标值)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= nums[left]) {
                // 说明在 ...left...mid...   [left, mid] 升序
                if(target == nums[mid]) {
                    return mid;
                } else if(target >= nums[left] && target < nums[mid]) {
                    // ...left...target...mid...
                    right = mid - 1;
                } else {
                    // target 可能 left...mid...target?...
                    left = mid + 1;
                }
            } else {
                // 说明 [mid, right] 是升序的
                if(target == nums[mid]) {
                    return mid;
                } else if(target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};
复制代码

解题思路是要确定 target 在哪个区间，剩下的就好办了，按照二分搜索的模板写就行了。

但是要注意 nums[mid] >= nums[left] 这个判断条件如：[3, 1]

81. 搜索旋转排序数组 II(有重复的元素，找目标值)

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left)/2;
            if(nums[mid] > nums[left]) {
                if(target == nums[mid]) {
                    return true;
                } else if(target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if(nums[mid] == nums[left]) {
                if(target == nums[left]) {
                    return true;
                } else {
                    left = left + 1;
                }
            } else {
                if(target == nums[mid]) {
                    return true;
                } else if(target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};
复制代码

和没有重复的一样思路，但是要处理重复的元素，所以单拎出来处理，因为不知道具体的情况，故只能一个一个的来。

153. 寻找旋转排序数组中的最小值(无重复元素，找最小值)

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

这个和旋转数组的写法一样，确定上升的和下降的区间，然后不断缩小空间

另一种写法是考虑右边，因为旋转之后右边的小的可能性较大，而且要考虑的条件也比较少

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

154. 寻找旋转排序数组中的最小值 II(有重复值，找最小值)

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

这个和没有重复值的思路一样，nums[mid] == nums[right] 的时候要特殊处理如下面的特殊用例：

// mid 在坐边
[2,2,2,2,2,2,2,2,2,0,2,2]
// mid 在右边
[2,2,0,2,2,2,2,2,2,2,2,2]
// 因为不能确定这两种情况，所以单拎出来处理，逐步向最小值靠拢
复制代码

峰值问题

这个问题是旋转数组的延续

162. 寻找峰值

二分

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 1;// [1, n - 1]
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid - 1] < arr[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};
复制代码

往常我们使用「二分」进行查值，需要确保序列本身满足「二段性」：当选定一个端点（基准值）后，结合「一段满足 & 另一段不满足」的特性来实现“折半”的查找效果。

但本题求的是峰顶索引值，如果我们选定数组头部或者尾部元素，其实无法根据大小关系“直接”将数组分成两段。

但可以利用题目发现如下性质：由于 arr 数值各不相同，因此峰顶元素左侧必然满足严格单调递增，峰顶元素右侧必然不满足。

因此 以峰顶元素为分割点的 arr 数组，根据与 前一元素/后一元素 的大小关系，具有二段性：

• 峰顶元素左侧满足 arr[i-1] < arr[i]arr[i−1]<arr[i] 性质，右侧不满足
• 峰顶元素右侧满足 arr[i] > arr[i+1]arr[i]>arr[i+1] 性质，左侧不满足

注意：计算 mid 的时候要向上取整，否则会死循环

三分

事实上，我们还可以利用「三分」来解决这个问题。

顾名思义，「三分」就是使用两个端点将区间分成三份，然后通过每次否决三分之一的区间来逼近目标值。

具体的，由于峰顶元素为全局最大值，因此我们可以每次将当前区间分为 [l, m1] 、**[m1,m2] ** 和 **[m2, r]**三段，如果满足 arr[m1] > arr[m2]，说明峰顶元素不可能存在与 [m2, r] 中，让 r = m2 – 1 即可。另外一个区间分析同理。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;// [1, n - 1]
        while(left < right) {
            int m1 = left + (right - left) / 3;
            int m2 = right - (right - left) / 3;
            if(arr[m1] > arr[m2]) {
                right = m2 - 1;
            } else {
                left = m1 + 1;
            }
        }
        return left;
    }
};
复制代码

852. 山脉数组的峰顶索引

参考

刷题路线