【LeetCode通關(guān)全記錄】35. 搜索插入位置
題目地址：35. 搜索插入位置
解法：二分查找
本題其實也是二分查找的變體。本題與二分查找的不同之處在于找不到待查元素時需要返回插入位置蔫仙，所以查不到時需要返回l——因為l左邊的值一直小于等于target辆毡，而r右邊的值一直大于等于target票从，這樣退出循環(huán)時朗徊，因為l左邊的值全部小于等于target所以l就是我們要求的插入位置。
另外這里用了一個小知識點：右移一位相當(dāng)于除以2池磁，并且比除法運算更快平窘。
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í)行用時: 4 ms（超過76.64%的Golang提交記錄）
內(nèi)存消耗: 3 MB（超過14.07%的Golang提交記錄）
時間復(fù)雜度：O(logn)，二分查找的時間復(fù)雜度為O(logn)跌榔；
空間復(fù)雜度：O(1)异雁，只使用了常數(shù)個數(shù)的存儲空間。
