算法之旅007 - 二分搜索Level1 Day7

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

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

167. Two Sum II - Input Array Is Sorted

经典的Two Sum，有其他解法，但这里是有序数组，按要求用二分法解，代码(Golang)如下：

    func twoSum(numbers []int, target int) []int {
        q := len(numbers) - 1
        for i, n := range numbers {
            m := target - n
            p := i + 1

            for p <= q {
                o := (p + q) / 2
                v := numbers[o]
                if v == m {
                    return []int{i + 1, o + 1}
                } else if v > m {
                    q = o - 1
                } else {
                    p = o + 1
                }
            }
        }
        return nil
    }

1608. Special Array With X Elements Greater Than or Equal X

找到一个数X，使数组中大于等X的元素个数等于X，注意X可以不是数组中的元素，代码(Golang)如下：

    func specialArray(nums []int) int {
        sort.Ints(nums)
        // fmt.Println(nums)

        helper := func(target int) int {
            i, j := 0, len(nums)-1
            for i <= j {
                k := (i + j) / 2
                // 找到第一个大于等于target的位置
                if nums[k] < target {
                    i = k + 1
                } else {
                    j = k - 1
                }
            }
            return j + 1
        }

        for i := 0; i <= nums[len(nums)-1]; i++ {
            q := helper(i)
            // fmt.Println(i, q)
            if len(nums)-q == i {
                return i
            }
        }
        return -1
    }

核心思想是：
1. 先排序数组
2. helper方法用来查找指定target插入有序数组时应该插入在哪个位置，和35. Search Insert Position类似
3. 从0遍历到数组最大值，找到一个i使得位置q之后有i个数字