11.2 排序数组中的二分查找

若数组是有序的或者部分有序, 都可以考虑尝试二分查找.

11.2.1 问题68: 查找插入位置

LCR 068. 搜索插入位置

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:

输入: nums = [1], target = 0
输出: 0

提示:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 为无重复元素的升序排列数组
• -10^4 <= target <= 10^4

11.2.1.1 分析&题解

使用二分查找, 若不存在的话, 插入位置满足:

• 所有值大于target, 插入首位即0
• 所有值小于target, 插入末尾即len(nums)
• 大于前一个, 小于后一个, 即$N_{i-1}< target< N_i$, 插入 i

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    
    // 二分查找
    for left <= right {
        mid := (left+right) / 2
        
        if nums[mid] >= target {
            // 边界: 插入最左边
            // 或 满足 nums[mid-1] < t <= nums[mid]
            if mid == 0 || nums[mid-1] < target {
                return mid
            }

            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    // 插入最右边
    return len(nums)
}

11.2.2 问题69: 山峰数组的顶部

LCR 069. 山脉数组的峰顶索引

符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：

• arr.length >= 3

• 存在i, 0 < i < arr.length - 1

  使得：

  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [1,3,5,4,2]
输出：2

示例 3：

输入：arr = [0,10,5,2]
输出：1

示例 4：

输入：arr = [3,4,5,1]
输出：2

示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

提示：

• 3 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^6
• 题目数据保证 arr 是一个山脉数组

**进阶：**很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？

11.2.2.1 分析&题解

使用二分查找, 若一个数字比两边的数都大那么它就是山峰.

1. 二分查找, 对于nums[mid]:

   1. 大于两边数, 则找到山峰
   2. 只是大于左边的数, 表示左侧是递增的, 山峰一定在右半边, 对右半边进行二分查找
   3. 只是大于右边的数, 表示右侧是递减的, 山峰一定在左半边, 对左半边进行二分查找

由于数字首尾的元素不可能成为山峰, 那么二分查找可以从[1, n-1]开始

func peakIndexInMountainArray(arr []int) int {
    // 二分
    left, right := 1, len(arr) - 2 
    
    for left <= right {
        mid := (left+right) / 2 
        
        // peek found
        if arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1] {
            return mid
        }

        // peek in right half
        if arr[mid] > arr[mid-1] {
            left = mid + 1
        } else { // peek in left half
            right = mid - 1
        }
    }

    return -1
}

11.2.3 问题70: 排序数组中只出现一次的数字

LCR 070. 有序数组中的单一元素

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

提示:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？

11.2.3.1 分析&题解

如果数字不是排序的话, 可以将数组元素全部进行异或运算, 最后结果一定是单独出现的元素. 时间O(n)

因为是排序的, 可以考虑使用二分查找来进行优化.

以1, 1, 2, 2, 3, 4, 4, 5, 5为例, 将数组元素两个一组分组之后得到(1,1) (2,2) (3,4) (4, 5) 5. 可以看出因为出现的单独的数字导致后序的分组元素全部不同, 那么第一个出现分组元素不同的分组的第一个元素就是那个只出现了一次的数字.

因为其他元素出现两次, 一个元素出现一次, 数组长度一定为奇数. 那么可以分成$\frac{n}{2}+1$ 组, 即$P_0, P_1, ..., P_{\frac{n}{2}}$.

对于分组$P_i$, 其第一个元素的下标为2i. 使用二分查找分组流程如下:

1. 对于中间分组$P_{mid}$, 若其元素不同:
   1. 其前一分组的元素相同或者$P_{mid} = P_0$ (为第一个分组), 那么此分组的第一个元素就是单独元素.
   2. 否则, 单独元素出现的分组在左半边
2. 其元素相同, 单独元素出现在右半边

func singleNonDuplicate(nums []int) int {
    // 二分查找分组 
    left, right := 0, len(nums)/2
    for left <= right {
        mid := (left + right) / 2
        // 分组第一个元素
        idx := 2 * mid
        
        // 组内元素不同
        if idx < len(nums)-1 && nums[idx] != nums[idx+1] {
            // 第一个分组 或 第一个元素不同的分组
            if mid == 0 || nums[idx-2] == nums[idx-1] {
                return nums[idx]
            }

            // 目标在左
            right = mid - 1
        } else { // 分组元素相同, 目标在右
            left = mid + 1
        }
    }

    // 最后一组只有一个元素
    return nums[len(nums)-1]
}

11.2.4 问题71: 按权重生成随机数

LCR 071. 按权重随机选择

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

示例 1：

输入：
inputs = ["Solution","pickIndex"]
inputs = [[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

输入：
inputs = ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
inputs = [[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。

提示：

• 1 <= w.length <= 10000
• 1 <= w[i] <= 10^5
• pickIndex 将被调用不超过 10000 次

11.2.4.1 分析&题解

对权重数组$a_0, a_1, ..., a_{n-1}$的元素和S, 在[0, S) 中生成的随机数p的概率为$\frac{1}{S}$ .

数组前i个元素和构建的数组可以表示为 $S_0, S_1, ..., S_{n-1}$.

对于随机数p, 若$S_i$是第一个大于p的数, 即$S_{i-1}\le p < S_i$, p取值范围中数字个数为 $S_i-S_{i-1} = a_i$, 选择下标i的概率就是 $\frac{a_i}{S}$ .

由上述可得流程:

1. 计算权重之和S, 在[0, S)中生成随机p
2. 构建前i个权重和数组
3. 二分查找寻找第一个大于随机数p的下标

type Solution struct {
    sums []int // 前i项权重和
    total int  // 权重和
}


func Constructor(w []int) Solution {
    sums := make([]int, 0, len(w))
    total := 0
    for _, n := range w {
        total += n
        sums = append(sums, total)
    }

    return Solution{sums: sums, total: total}
}


func (s *Solution) PickIndex() int {
    p := rand.Intn(s.total)

    // 二分查找第一个大于 p 的
    left, right := 0, len(s.sums)-1
    for left <= right {
        mid := (left + right) / 2
        
        if s.sums[mid] > p {
            // 首个元素 或 第一个大于 p
            if mid == 0 || s.sums[mid-1] <= p {
                return mid
            } 

            // 左
            right = mid - 1
        } else {
            // 右
            left = mid + 1
        }
    }

    return -1
}

Reference

1. 剑指Offer（专项突破版）