二分查找是一种在有序列表中查找元素的高效方法，时间复杂度（logN），二分查找思路和时间都比较简单，但是实际问题中的细节不可忽视。

3.1 搜索插入位置

LeetCode No.35

问题描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置，你可以假设数组中无重复元素。

思路：按照二分查找法，定义low，high两个指针，结束条件为low > high，如果目标值不存在返回low的位置就是要插入的位置。

示例代码：

func searchInsert(nums []int, target int) int {
    l, h := 0, len(nums) - 1
    var m int
    for l <= h {
        m = h + l >> 1
        if nums[m] == target {
            return m
        }
        if nums[m] > target {
            h = m - 1
        } else {
            l = m + 1
        }
    }
    return l
}

3.2 搜索旋转排序数组

LeetCode No.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

思路：进行二分之后的mid位置元素位置可能有两种情况：左边元素的所有元素是有序的，或右边的所有元素是有序的。

• 如果是左边有序，则nums[mid] > nums[low]，反之是右边有序
• 在知道是那边有序后即可根据边界和target来选择去左半区还是右半区搜索

示例代码：

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

3.3 排序数组中查找元素的第一个和最后一个位置（有重复元素）

LeetCode No.34

问题描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置，如果数组中不存在目标值 target，返回 [-1, -1]。

思路：找到最左边的target位置和target+1最左边的位置-1，要找最左边的target，那么当nums[mid] >= target时都要继续往左半区搜索。

示例代码：

func searchRange(nums []int, target int) []int {
    ledge := search(nums, target)
    if ledge == len(nums) || nums[ledge] != target {
        return []int{-1, -1}
    }
    redge := search(nums, target + 1) - 1
    return []int{ledge, redge}
}

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