二分查找是一種在有序列表中查找元素的高效方法，時間復(fù)雜度（logN），二分查找思路和時間都比較簡單，但是實際問題中的細(xì)節(jié)不可忽視。

3.1 搜索插入位置

LeetCode No.35

問題描述：給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置，你可以假設(shè)數(shù)組中無重復(fù)元素。

思路：按照二分查找法，定義low，high兩個指針，結(jié)束條件為low > high，如果目標(biāo)值不存在返回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 搜索旋轉(zhuǎn)排序數(shù)組

LeetCode No.33

問題描述：整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值 互不相同 。在傳遞給函數(shù)之前，nums 在預(yù)先未知的某個下標(biāo) k（0 <= k < nums.length）上進(jìn)行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標(biāo) 從 0 開始 計數(shù)）。例如， [0,1,2,4,5,6,7] 在下標(biāo) 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。
給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個整數(shù) target ，如果 nums 中存在這個目標(biāo)值 target ，則返回它的索引，否則返回 -1

思路：進(jìn)行二分之后的mid位置元素位置可能有兩種情況：左邊元素的所有元素是有序的，或右邊的所有元素是有序的。

• 如果是左邊有序，則nums[mid] > nums[low]，反之是右邊有序
• 在知道是那邊有序后即可根據(jù)邊界和target來選擇去左半?yún)^(qū)還是右半?yún)^(qū)搜索

示例代碼：

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 排序數(shù)組中查找元素的第一個和最后一個位置（有重復(fù)元素）

LeetCode No.34

問題描述：給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置，如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

思路：找到最左邊的target位置和target+1最左邊的位置-1，要找最左邊的target，那么當(dāng)nums[mid] >= target時都要繼續(xù)往左半?yún)^(qū)搜索。

示例代碼：

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
}