更多精彩內(nèi)容，請(qǐng)關(guān)注【力扣簡(jiǎn)單題】臊旭。
題目
難度：
類型：數(shù)組
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值离熏，在數(shù)組中找到目標(biāo)值戴涝，并返回其索引啥刻。如果目標(biāo)值不存在于數(shù)組中可帽，返回它將會(huì)被按順序插入的位置映跟。
你可以假設(shè)數(shù)組中無重復(fù)元素。
示例
示例 1:
輸入: [1,3,5,6], 5
輸出: 2
示例 2:
輸入: [1,3,5,6], 2
輸出: 1
示例 3:
輸入: [1,3,5,6], 7
輸出: 4
示例 4:
輸入: [1,3,5,6], 0
輸出: 0
解答
這是一道典型的二分法問題辜昵。我們將整個(gè)數(shù)組看成一條線段路鹰，將這條線斷從中間切開晋柱，查看線段中間位置所在的值和插入數(shù)之間的大小關(guān)系雁竞，根據(jù)此大小關(guān)系可以拋棄一半線段碑诉。
這里需要注意的有：
初始化进栽，用兩個(gè)端點(diǎn)下標(biāo)left和right進(jìn)行代表當(dāng)前研究的線段快毛，分別設(shè)置成數(shù)組兩端數(shù)字下標(biāo)番挺；
控制條件玄柏，只要左端點(diǎn)不大于右端點(diǎn)粪摘，即可執(zhí)行循環(huán)過程徘意，這樣做也可以解決輸入數(shù)組僅有一個(gè)元素的情況映砖；
最后跳出循環(huán)后返回值（插入target的位置）必須是左端點(diǎn)坐標(biāo)，如果輸入為空時(shí)劳澄，應(yīng)該返回0秒拔，即不執(zhí)行循環(huán)。
class Solution:
def searchInsert(self, nums, target):
left, right = 0, len(nums)-1 # 初始化左右端點(diǎn)位置
while left <= right: # 當(dāng)條件合法時(shí)
mid = left + (right - left) // 2 # 獲取中點(diǎn)飒硅，如果是偶數(shù)取靠左的位置
if nums[mid] == target: # 找到該數(shù)
return mid # 直接返回
elif nums[mid] > target: # 如果當(dāng)前位置數(shù)比插入值大
right = mid - 1 # 更新右端點(diǎn)
else: # 如果當(dāng)前位置數(shù)比插入值小
left = mid + 1 # 更新左端點(diǎn)
return left # 返回插入位置砂缩，這里是左端位置
如有疑問或建議，歡迎評(píng)論區(qū)留言~
