二分搜索

参考
https://www.cnblogs.com/kyoner/p/11080078.html

https://leetcode-cn.com/problems/find-k-th-smallest-pair-distance/solution/chi-tou-er-fen-fa-xi-lie-cong-ru-men-dao-2eh6/
二分搜索.pdf

寻找一个数

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意
    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

寻找左侧边际

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

寻找右侧边界

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n)的算法来解决此问题。

示例 1：
输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

暴力

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        idx = 0
        for i in range(1, len(nums)):
            if nums[i] > nums[idx]:
                idx = i
        return idx


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode-solution-96sj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

爬坡法
方法二：迭代爬坡

思路与算法

俗话说「人往高处走，水往低处流」。如果我们从一个位置开始，不断地向高处走，那么最终一定可以到达一个峰值位置。

因此，我们首先在 [0,n)[0, n)[0,n) 的范围内随机一个初始位置 iii，随后根据 nums[i−1],nums[i],nums[i+1]\textit{nums}[i-1], \textit{nums}[i], \textit{nums}[i+1]nums[i−1],nums[i],nums[i+1] 三者的关系决定向哪个方向走：

如果 nums[i−1]<nums[i]>nums[i+1]\textit{nums}[i-1] < \textit{nums}[i] > \textit{nums}[i+1]nums[i−1]<nums[i]>nums[i+1]，那么位置 iii 就是峰值位置，我们可以直接返回 iii 作为答案；

如果 nums[i−1]<nums[i]<nums[i+1]\textit{nums}[i-1] < \textit{nums}[i] < \textit{nums}[i+1]nums[i−1]<nums[i]<nums[i+1]，那么位置 iii 处于上坡，我们需要往右走，即 i←i+1i \leftarrow i+1i←i+1；

如果 nums[i−1]>nums[i]>nums[i+1]\textit{nums}[i-1] > \textit{nums}[i] > \textit{nums}[i+1]nums[i−1]>nums[i]>nums[i+1]，那么位置 iii 处于下坡，我们需要往左走，即 i←i−1i \leftarrow i-1i←i−1；

如果 nums[i−1]>nums[i]<nums[i+1]\textit{nums}[i-1] > \textit{nums}[i] < \textit{nums}[i+1]nums[i−1]>nums[i]<nums[i+1]，那么位置 iii 位于山谷，两侧都是上坡，我们可以朝任意方向走。

如果我们规定对于最后一种情况往右走，那么当位置 iii 不是峰值位置时：

如果 nums[i]<nums[i+1]\textit{nums}[i] < \textit{nums}[i+1]nums[i]<nums[i+1]，那么我们往右走；

如果 nums[i]>nums[i+1]\textit{nums}[i] > \textit{nums}[i+1]nums[i]>nums[i+1]，那么我们往左走。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        idx = random.randint(0, n - 1)

        # 辅助函数，输入下标 i，返回 nums[i] 的值
        # 方便处理 nums[-1] 以及 nums[n] 的边界情况
        def get(i: int) -> int:
            if i == -1 or i == n:
                return float('-inf')
            return nums[i]

        while not (get(idx - 1) < get(idx) > get(idx + 1)):
            if get(idx) < get(idx + 1):
                idx += 1
            else:
                idx -= 1

        return idx

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode-solution-96sj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二分法

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)

        # 辅助函数，输入下标 i，返回 nums[i] 的值
        # 方便处理 nums[-1] 以及 nums[n] 的边界情况
        def get(i: int) -> int:
            if i == -1 or i == n:
                return float('-inf')
            return nums[i]

        left, right, ans = 0, n - 1, -1
        while left <= right:
            mid = (left + right) // 2
            if get(mid - 1) < get(mid) > get(mid + 1):
                ans = mid
                break
            if get(mid) < get(mid + 1):
                left = mid + 1
            else:
                right = mid - 1

        return ans


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode-solution-96sj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3：
输入：nums = [1], target = 0 输出：-1

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

官方题解
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/

朴素解法

但凡是从有序序列中找某个数，我们第一反应应该是「二分」。

这道题是一个原本有序的数组在某个点上进行了旋转，其实就是将原本一段升序的数组分为了两段。

我们可以先找到旋转点 idx，然后对 idx 前后进行「二分」。

作者：AC_OIer
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/shua-chuan-lc-yan-ge-ologn100yi-qi-kan-q-xifo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int idx = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                idx = i;
                break;
            }
        }
        int ans = find(nums, 0, idx, target);
        if (ans != -1) return ans;
        if (idx + 1 < n) ans = find(nums, idx + 1, n - 1, target);
        return ans;
    }
    int find(int[] nums, int l, int r, int target) {
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l] == target ? l : -1;
    }
}


作者：AC_OIer
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/shua-chuan-lc-yan-ge-ologn100yi-qi-kan-q-xifo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。

1891. 割绳子

给定一个整数数组 ribbons 和一个整数 k，数组每项 ribbons[i] 表示第 i 条绳子的长度。对于每条绳子，你可以将任意切割成一系列长度为正整数的部分，或者选择不进行切割。
例如，如果给你一条长度为 4 的绳子，你可以：

• 保持绳子的长度为 4 不变；
• 切割成一条长度为 3 和一条长度为 1 的绳子；
• 切割成两条长度为 2 的绳子；
• 切割成一条长度为 2 和两条长度为 1 的绳子；
• 切割成四条长度为 1 的绳子。

你的任务是最终得到 k 条完全一样的绳子，他们的长度均为相同的正整数。如果绳子切割后有剩余，你可以直接舍弃掉多余的部分。
对于这 k 根绳子，返回你能得到的绳子最大长度；如果你无法得到 k 根相同长度的绳子，返回 0。

示例 1:
输入: ribbons = [9,7,5], k = 3 输出: 5 解释: - 把第一条绳子切成两部分，一条长度为 5，一条长度为 4； - 把第二条绳子切成两部分，一条长度为 5，一条长度为 2； - 第三条绳子不进行切割； 现在，你得到了 3 条长度为 5 的绳子。
示例 2:
输入: ribbons = [7,5,9], k = 4 输出: 4 解释: - 把第一条绳子切成两部分，一条长度为 4，一条长度为 3； - 把第二条绳子切成两部分，一条长度为 4，一条长度为 1； - 把第二条绳子切成三部分，一条长度为 4，一条长度为 4，还有一条长度为 1； 现在，你得到了 4 条长度为 4 的绳子。
示例 3:
输入: ribbons = [5,7,9], k = 22 输出: 0 解释: 由于绳子长度需要为正整数，你无法得到 22 条长度相同的绳子。

提示:

• 1 <= ribbons.length <= 105
• 1 <= ribbons[i] <= 105
• 1 <= k <= 109

通过次数389
提交次数862

难以理解版

class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
        left = 1 # 初始值取0 或1都可以
        right = max(ribbons) # 上限取最大值是因为 对一条绳子，可以根据mid拆分为多段
        while left <= right:
            mid = left + (right - left) // 2
            if self.check(ribbons, mid, k):
                left = mid + 1
            else:
                right = mid - 1
        return right

    def check(self, ribbons, mid, k):
        temp = 0
        if mid == 0 : # 防止除以0
             return True
        for i in ribbons:
            temp += i // mid
        return temp >= k

不知道最后返回是 right还是 left - 1

好理解版
使用res 保存二分搜索中的值

class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
        left = 1 # 初始值取0 或1都可以
        right = max(ribbons) # 上限取最大值是因为 对一条绳子，可以根据mid拆分为多段
        res = 0
        while left <= right:
            mid = left + (right - left) // 2
            if self.check(ribbons, mid, k):
                res = mid
                left = mid + 1
            else:
                right = mid - 1
        return res

    def check(self, ribbons, mid, k):
        temp = 0
        if mid == 0 :
             return True
        for i in ribbons:
            temp += i // mid
        return temp >= k

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3：
输入：nums = [1], target = 0 输出：-1

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

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

719. 找出第 k 小的距离对

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
示例 1:
输入： nums = [1,3,1] k = 1 输出：0 解释： 所有数对如下： (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。
提示:

1. 2 <= len(nums) <= 10000.
2. 0 <= nums[i] < 1000000.
3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

通过次数9,704
提交次数25,817