跟着LeetCode的Study Plan重温一遍各种经典算法，本期是二分搜索算法Level1 Day6。
题目构成：Easy*2。
找第一个符合条件的index，使其按等差数列求和的值小于等于n，代码(Golang)如下：
func arrangeCoins(n int) int {
i, j := 1, n
for i <= j {
m := (i + j) / 2
v := m * (m + 1) / 2 // 等差数列求和
if v == n {
return m
} else if v > n {
j = m - 1
} else {
i = m + 1
}
}
return j
}
在递增数组中查找第k个缺失的数，代码(Golang)如下：
func findKthPositive(arr []int, k int) int {
i, j := 0, len(arr)-1
for i <= j {
m := (i + j) / 2
v := arr[m] - m - 1 // m左边有几个缺失的数字
// 找arr中第一个index，其左边的缺失数大于等于k
if v >= k {
// 等于的情况不能直接返回，因为可能不是等一个符合情况的数字
j = m - 1
} else {
i = m + 1
}
}
// 此时j + 1 是arr中第一个index，其左边的缺失数大于等于k，加上k之后就是目标值了
return j + k + 1
}
核心思想是：
1. 数组中的元素是从1开始的，因此v := arr[m] - m - 1表示m左边有几个缺失的数字
2. 二分搜索找到位置j，此时j + 1是arr中第一个左边的缺失数大于等于k的位置
3. j + k + 1表示第k个缺失数，也就是答案