算法之旅005 - 二分搜索Level1 Day5

跟着LeetCode的Study Plan重温一遍各种经典算法，本期是二分搜索算法Level1 Day5。

题目构成：Easy*1 + Medium*1。

278. First Bad Version

找第一个符合条件的index，代码(Golang)如下：

    func firstBadVersion(n int) int {
        i, j := 1, n
        for i <= j {
            m := (i + j) / 2
            // fmt.Println(i, m, j)
            if isBadVersion(m) {
                j = m - 1
            } else {
                i = m + 1
            }
        }
        return i
    }

34. Find First and Last Position of Element in Sorted Array

在非递减数组中查找目标值的起止范围，代码(Golang)如下：

    func searchRange(nums []int, target int) []int {
        r := []int{-1, -1}
        i, j := 0, len(nums)-1
        for i <= j {
            m := (i + j) / 2
            v := nums[m]
            if v == target {
                // 找右边界
                m1 := m
                for m1 <= j {
                    mr := (m1 + j) / 2
                    vr := nums[mr]
                    if vr > target {
                        j = mr - 1
                    } else {
                        m1 = mr + 1
                    }
                }

                // 找左边界
                m2 := m
                for i <= m2 {
                    ml := (i + m2) / 2
                    vl := nums[ml]
                    if vl < target {
                        i = ml + 1
                    } else {
                        m2 = ml - 1
                    }
                }

                return []int{i, j}
            } else if v < target {
                i = m + 1
            } else {
                j = m - 1
            }
        }
        return r
    }

核心思想是：
1. 先用外层的正常二分找到一个等于目标值的位置m
2. 在当前i和m之间找到等于目标值的左边界
3. 在当前j和m之间找到等于目标值的右边界