【LeetCode通關(guān)全記錄】35. 搜索插入位置

題目地址：35. 搜索插入位置

解法：二分查找

本題其實(shí)也是二分查找的變體。本題與二分查找的不同之處在于找不到待查元素時(shí)需要返回插入位置，所以查不到時(shí)需要返回l——因?yàn)?code>l左邊的值一直小于等于target，而r右邊的值一直大于等于target，這樣退出循環(huán)時(shí)，因?yàn)?code>l左邊的值全部小于等于target所以l就是我們要求的插入位置。

另外這里用了一個(gè)小知識(shí)點(diǎn)：右移一位相當(dāng)于除以2，并且比除法運(yùn)算更快。

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

執(zhí)行用時(shí): 4 ms（超過(guò)76.64%的Golang提交記錄）

內(nèi)存消耗: 3 MB（超過(guò)14.07%的Golang提交記錄）

時(shí)間復(fù)雜度：O(logn)，二分查找的時(shí)間復(fù)雜度為O(logn)；

空間復(fù)雜度：O(1)，只使用了常數(shù)個(gè)數(shù)的存儲(chǔ)空間。