二分查找

1. 二分查找简介

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 [1]
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

注意：这是百度百科给予二分查找的定义。但我认为二分查找中元素不一定是严格有序的。只要每次都有一定的条件舍弃左半部分或右半部分都可以统称为二分查找，时间复杂度也是Logn。

2. 二分查找架构

left  := 0
right := len(nums)-1
for left <= right{
    mid := left + (right-left)/2
    if nums[mid] <= target{
        right = mid + 1   //注意,如果是left<right,这里要取right=mid
    }else{
        left = mid - 1
    }
}
return left

3. 二分查找经典题目必须 掌握

704. 二分查找 简单

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

题解概要：

1. 套用二分法模板即可

代码：

func search(nums []int, target int) int {
    left  := 0
    right := len(nums)-1
    for left <= right{
        mid := left + (right-left) / 2    
        if nums[mid] < target{
            left = mid + 1
        }else if nums[mid] > target{
            right = mid - 1
        }else{
            return mid
        }
    }
    return -1
}

69. Sqrt(x) 简单

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：
输入：x = 4
输出：2

示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 231 - 1

题解概要：

1. 套用二分法模板即可,注意最后返回的是right

代码：

func mySqrt(x int) int {
    left  := 0
    right := x 
    for left <= right{
        num := (left + right) / 2
        if num * num <= x{
            left = num + 1
        }else if num * num > x{
            right = num - 1
        }
    }
    return right
}

35. 搜索插入位置 简单

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

请必须使用时间复杂度为 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 <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

题解概要：

1. 套用二分法模板即可。

代码：

func searchInsert(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left <= right{
        mid := left +(right-left)/2
        if nums[mid] == target{
            return mid
        }
        if nums[mid] < target{
            left = mid + 1
        }else{
            right = mid - 1
        }
    }
    return left
}

852. 山脉数组的峰顶索引 简单

符合下列属性的数组 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 = [0,2,1,0]
输出：1

示例 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 <= 104
0 <= arr[i] <= 106
题目数据保证 arr 是一个山脉数组

题解概要：

1. 套用二分法模板即可以求出答案，但要注意是arr[mid]与arr[mid+1]的边界问题。

代码：

func peakIndexInMountainArray(arr []int) int {
    left := 0 
    right := len(arr)-1
    for left < right{
        mid := left + (right-left) / 2
        if arr[mid] > arr[mid+1]{
            right = mid
        }else{
            left = mid + 1
        }
    }
    return left
}

剑指 Offer 53 - II. 0～n-1中缺失的数字 简单

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:
输入: [0,1,3]
输出: 2

示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：
1 <= 数组长度 <= 10000

题解概要：

1. 本题的判断条件是mid索引与mid代表值之间的关系。

代码：

func missingNumber(nums []int) int {
    left := 0
    right := len(nums)-1
    for left <= right{
        mid := left + (right-left) / 2
        if nums[mid] == mid {
            left = mid + 1
        }else{
            right = mid-1
        }
    }
    return left
}

1539. 第 k 个缺失的正整数 简单

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

示例 1：
输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,…] 。第 5 个缺失的正整数为 9 。

示例 2：
输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,…] 。第 2 个缺失的正整数为 6 。

提示：
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j]

题解概要：

1. 本题难点是找到缺失数字的关系。可以利用数学公式进行递推。

代码：

func findKthPositive(arr []int, k int) int {
    left := 0 
    right := len(arr)-1
    for left <= right{
        mid := left + (right-left) / 2
        if arr[mid] - mid <= k {
            left = mid + 1
        }else{
            right = mid - 1
        }
    }
    return left + k
}

4. 旋转数组题目必须 掌握

剑指 Offer 11. 旋转数组的最小数字 简单

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。

示例 1：
输入：[3,4,5,1,2]
输出：1

示例 2：
输入：[2,2,2,0,1]
输出：0

题解概要：

1. 本题判断是中间数与有边界数的关系。因为有重复数字，所以当重复时，right—即可。

代码：

func minArray(numbers []int) int {
    left := 0 
    right:= len(numbers)-1
    for left < right{
        mid := left + (right-left) / 2
        if numbers[mid] > numbers[right]{
            left = mid + 1
        }else if numbers[mid] == numbers[right]{
            right --
        }else{
            right = mid
        }
    }
    return numbers[left]
}

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

题解概要：

因为原数组是严格升序的，因此旋转后的数组可以分为两部分的严格升序，借鉴二分法进行查找。
注意到，这两部分的大小关系如图所示：

分为左半部分与右半部分

首先初始化 left = 0, right = length-1
计算 mid = (left + right) / 2
判断 mid 在哪个部分
若 nums[mid] >= nums[left]，则在左半部分
若 nums[mid] < target，说明 target 只可能在 B 段
若 nums[mid] > target，说明 target 可能在 A 段或 C 段
先判断是否在 A 段 nums[mid] > target && target >= nums[left]

若 nums[mid] < nums[left]，则在右半部分
若 nums[mid] > target，说明 target 只可能在 A 段
若 nums[mid] < target，说明 target 可能在 B 段或 C 段
先判断是否在 B 段：nums[mid] < target && target <= nums[right]

代码：

func search(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left <= right{
        mid := left + (right-left) / 2
        if nums[mid] == target{
            return mid
        }
        if nums[mid] >= nums[left]{
            if nums[mid] > target && target>=nums[left]{    //一定要注意这个条件
                right = mid - 1
            }else{
                left = mid + 1
            }
        }else{
            if nums[mid] < target && target <= nums[right]{//一定要注意这个条件
                left = mid + 1
            }else{
                right = mid - 1
            } 
        }
    }
    return -1
}

81. 搜索旋转排序数组 II 中等

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

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

提示：
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

题解概要：

与33题的整体思路一致，只是遇到重复时，需要判断一下。

代码：

func search(nums []int, target int) bool {
    left,right := 0,len(nums) - 1
    for left <= right{
        mid := left + (right - left) / 2
        if nums[mid] == target{
            return true
        }
        if nums[mid] == nums[left]{
            left ++
            continue
        }else if nums[mid] > nums[left]{
            if nums[mid] > target && target >= nums[left]{
                right = mid - 1
            }else{
                left = mid + 1
            }
        }else{
            if nums[mid] < target && target <= nums[right]{
                left = mid + 1
            }else{
                right = mid - 1
            }
        }
    }   
    return false
}

面试题 10.03. 搜索旋转数组 中等

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）

示例2:
输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）

提示:

1. arr 长度范围在[1, 1000000]之间

题解概要：

和81题的思路一致，因为此题是返回索引最小的一个，需要多加一些判断。

代码：

func search(arr []int, target int) int {
    left,right := 0,len(arr) - 1
    for left <= right{
        mid := left + (right - left) / 2
        if arr[left] == target{
            return left
        }
        if arr[mid] == target{
            right = mid
            continue
        }
        if arr[mid] == arr[left]{
            left ++
            continue        
        }else if arr[mid] > arr[left]{
            if arr[mid] > target && target >= arr[left]{
                right = mid - 1
            }else{
                left = mid + 1
            }
        }else{
            if arr[mid] < target && target <= arr[right]{
                left = mid + 1
            }else{
                right = mid - 1
            }
        }
    }
    return -1
}

154. 寻找旋转排序数组中的最小值 II 困难

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：
输入：nums = [1,3,5]
输出：1

示例 2：
输入：nums = [2,2,2,0,1]
输出：0

提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

题解概要：

1. 本题判断是中间数与有边界数的关系。因为有重复数字，所以当重复时，right—即可。

代码：

func findMin(nums []int) int {
    left := 0
    right:=len(nums)-1
    for left < right{
        mid := left + (right-left) / 2
        if nums[mid] > nums[right]{
            left = mid + 1
        }else if nums[mid] == nums[right]{
            right --
        }else{
            right = mid
        }
    }
    return nums[left]
}

5. 矩阵中的查找必须 掌握

剑指 Offer 04. 二维数组中的查找 中等

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:
现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

限制：
0 <= n <= 1000
0 <= m <= 1000

题解概要：

1. 本题可以从右上角开始。如果当前数小于目标值，则往下移动，否则往左移动。

代码：

func findNumberIn2DArray(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false 
    }
    col := len(matrix[0])-1
    row := 0
    for col >= 0 && row < len(matrix){
        num := matrix[row][col]
        if num > target{
            col --
        }else if num == target{
            return true
        }else{
            row ++
        }
    }
    return false
}

378. 有序矩阵中第 K 小的元素 中等

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

示例 1：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：
输入：matrix = [[-5]], k = 1
输出：-5

提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
1 <= k <= n2

题解概要：

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/you-xu-ju-zhen-zhong-di-kxiao-de-yuan-su-by-leetco/

代码：

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    left := matrix[0][0]
    right := matrix[n-1][n-1]
    for left < right{
        mid := left + (right-left)/2
        if check(mid,matrix,k){
            right = mid 
        }else{
            left = mid + 1
        }
    }
    return left
}
func check(mid int,matrix [][]int,k int)bool{
    //统计小于mid的个数
    i := len(matrix)-1
    j := 0
    num := 0
    for i >= 0 && j < len(matrix){
        if matrix[i][j] <= mid{
            num += i+1
            j ++        
        }else{
            i--
        }
    }
    return num >= k
}

6. 二分查找其他相关题目必须 掌握

34. 在排序数组中查找元素的第一个和最后一个位置 中等

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

题解概要：

1. 本道题可以先找到元素第一次出现的位置，再找到最后一次出现的位置，这样时间复杂度是2logn。

代码：

func searchRange(nums []int, target int) []int {
    /*找到第一次出现的位置*/
    l := 0
    r := len(nums)-1
    for l <= r{
        mid := l + (r-l) / 2
        if target <= nums[mid]{
            r = mid - 1
        }else{
            l = mid + 1
        }
    }
    /*找到最后一次出现的位置*/
    left := 0
    right := len(nums)-1
    for left <= right{
        mid := left + (right-left) / 2
        if target < nums[mid]{
            right = mid - 1
        }else{
            left = mid + 1
        }
    }
    if l <= right{
        return []int{l,right}
    }else{
        return []int{-1,-1}
    }
}

633. 平方数之和 中等

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：
输入：c = 5
输出：true
解释：1 1 + 2 2 = 5

示例 2：
输入：c = 3
输出：false

提示：
0 <= c <= 231 - 1

题解概要：

1. 这道题使用双指针法更好理解。

代码：

func judgeSquareSum(c int) bool {
    left  := 0
    right := int(math.Ceil(math.Sqrt(float64(c))))
    for left <= right{
        num := left * left + right * right
        if num > c{
            right -- 
        }else if num < c{
            left ++ 
        }else{
            return true
        }
    }
    return false
}

540. 有序数组中的单一元素 中等

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 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 <= 105
0 <= nums[i] <= 105

题解概要：

1. 如果mid之前唯一的数没有出现过，那么mid这一对数的索引一定是偶数与奇数。
2. 可以先判断mid是偶数还是奇数，再判断mid与mid+1的关系。

代码：

func singleNonDuplicate(nums []int) int {
    left := 0
    right := len(nums)-1
    //观察例子我们可以发现，在题目要求的数字（出现一次的数字）之前，两个重复的数字的位置是偶-奇，但是出现之后两个重复的数字就变成的奇-偶。
    for left < right{
        mid := left + (right-left)/2
        if mid & 1 == 0{
            //判断偶奇是否出现
            if nums[mid+1] == nums[mid]{
                left = mid + 1
            }else{
                right = mid
            }
        }else{
            //判断奇偶是否出现
            if nums[mid] == nums[mid+1]{
                right = mid -1
            }else{
                left =     mid + 1
            }
        }
    }
    return nums[left]
}

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]

代码：

func findPeakElement(nums []int) int {
    l,r := 0,len(nums) - 1
    for l < r{
        //典型的二分查找
        mid := l + (r - l) / 2
        if nums[mid] > nums[mid+1]{
            r = mid
        }else{
            l = mid + 1
        }
    }
    return l
}

287. 寻找重复数 中等

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：
输入：nums = [1,3,4,2,2]
输出：2

示例 2：
输入：nums = [3,1,3,4,2]
输出：3

提示：
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

题解概要：

https://leetcode-cn.com/problems/find-the-duplicate-number/solution/shu-ju-jie-gou-he-suan-fa-er-fen-fa-cha-8ybnw/抽屉原理

代码：

func findDuplicate(nums []int) int {
    left,right := 0,len(nums) - 1
    for left < right{
        mid := left + (right - left) / 2
        cnt := 0
        for _,v := range nums{
            if v <= mid{
                cnt ++
            }
        }
        if cnt > mid{
            right = mid
        }else{
            left = mid + 1
        }
    }
    return left
}