[Go版]算法通关村第九关白银——二分查找与搜索树高频问题

基于二分查找的拓展问题

题目：山脉数组的峰顶索引

题目链接：LeetCode-852. 山脉数组的峰顶索引

思路分析：arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1]

1. 使用二分查找法，目标索引的条件：arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1]
2. 其余还剩两种状态处理左右边界：
   • 上坡状态arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1]时：left = mid+1
   • 下坡状态arr[mid-1] > arr[mid] && arr[mid] > arr[mid+1]时：right = mid-1
3. 其他注意：
   • 要形成山峰至少需要3个元素
   • left、right的初始值为1和length-2，因为峰顶不可能是首位元素，可以直接排除

Go代码

func peakIndexInMountainArray(arr []int) int {
    length := len(arr)
    if length < 3 {
        return -1
    }
    left, right := 1, length-2  //不可能是首位元素，可以直接排除
    for left <= right {
        mid := (right-left)>>1 + left
        if arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1] {
            return mid
        } else if arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1] { //上坡
            left = mid+1
        } else {    //下坡
            right = mid-1
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目：旋转数字的最小数字

题目链接：LeetCode-153. 寻找旋转排序数组中的最小值

思路分析：arr[mid] 和 arr[right] 比大小定边界

1. 使用二分查找法
2. 有两种状态处理边界：
   • arr[mid]>arr[right]即最小值的左边时：left = mid+1 （这里为什么+1，因为arr[mid]都大于别的数了，说明肯定不可能是它，所以可以跳过它）
   • arr[mid]<arr[right]即最小值的右边时：right=mid（这里为什么不+1，因为这里只能看出arr[mid]小于另一个数，但不知道它是不是最小的，有这个可能，所以需要再和别的进行对比）
3. 最后return arr[right]（根据实际举例画图可知）

Go代码

func findMin(nums []int) int {
    length := len(nums)
    left, right := 0, length-1
    for left<right {
        mid := (right-left)>>1 + left
        if nums[mid] > nums[right] {    //最小值左边
            left = mid+1
        } else {    //最小值右边
            right = mid
        }
    }
    return nums[right]
}
1
2
3
4
5
6
7
8
9
10
11
12
13

题目：找缺失数字

题目链接：LeetCode-剑指 Offer 53 - II. 0～n-1中缺失的数字

思路分析：arr[i] != i

1. 根据题意，可以明确目标数字为：arr[i] != i 时的 i
2. 有其余两种状态：
   • 相等状态arr[i]==i时：left=mid+1
   • 不相等状态arr[i]!=i时：right=mid-1，每次更新right之前，用一个变量find接收mid的值，当跳出循环时，该变量就是目标值。
3. 最后 return find

Go代码

func missingNumber(nums []int) int {
    length := len(nums)
    left, right := 0, length-1
    find := length
    for left <= right {
        mid := (right-left)>>1 + left
        if nums[mid] == mid {
            left = mid+1
        } else {
            find = mid
            right = mid-1
        }
    }
    return find
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题目：优化求平方根

题目链接：LeetCode-69. x 的平方根

思路分析：x/mid==mid

1. 使用二分查找法，目标值条件：x/mid == mid
2. 有两种状态：
   • x/mid > mid：代表除少了（比如 8/2 > 2），left=mid+1
   • x/mid < mid：代表除多了（比如 8/4 < 4），right=mid-1
3. 最后return right（根据实际举例画图可知）

Go代码

func mySqrt(x int) int {
    left, right := 1, x
    for left <= right {
        mid := (right-left)>>1 + left
        if x/mid == mid {
            return mid
        } else if x/mid < mid { //除多了
            right = mid-1
        } else {    //除少了
            left = mid+1
        }
    }
    return right
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

中序和搜索树原理

题目：二叉搜索树中搜索特定值

题目链接：LeetCode-700. 二叉搜索树中的搜索

思路分析：二叉搜索树特点（left子节点值 < 根节点值 < right子节点值）

1. 因为二叉搜索树的特点：其left子节点的值 < 根节点的值 < 其right子节点的值，所以可以使用二分查找法
2. 目标节点的条件：root.Val == val
3. 其余两种情况：
   • root.Val < val时：在root的Right部分寻找
   • root.Val > val时：在root的Left部分寻找
4. 如果都没有找到的话就返回nil

Go代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil && root.Val != val {
        if root.Val > val {
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目：验证二叉搜索树

题目链接：LeetCode-98. 验证二叉搜索树

思路分析：二叉搜索树特点（中序遍历二叉搜索树会得到一个升序的数组）

1. 根据二叉搜索树的特点：对二叉搜索树中序遍历后会得到一个升序的数组。
2. 对二叉搜索树进行中序遍历，在遍历过程中，如果发现当前节点和上一个节点不是升序时，就说明不是二叉搜索树。
3. 如果遍历完都是升序的，则是二叉搜索树。

Go代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    isFirst := true
    var min int //用于缓存当前最小值
    var a func(*TreeNode) bool
    a = func(root *TreeNode) bool {
        if root == nil {
            return true
        }
        if !a(root.Left) {
            return false
        }
        // 最左叶子树时：直接跳过比值判断
        if isFirst {
           isFirst = false
        } else if root.Val <= min {
            return false
        }
        min = root.Val
        return a(root.Right)
    }
    return a(root)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30