一、題目要求

給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為?O(log n)?的算法

示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例?2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

二、解決

因為題目要求時間復雜度為O(logn)，因此這道題屬于基礎的利用二分查找的方法查找。

示例代碼如下所示：

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left = 0right = len(nums) -1while left <= right:mid = (left+right) // 2if nums[mid] == target:return midelif nums[mid] > target:right = mid -1else:left = mid +1else:return right+1

注意點

需要滿足如果找不到target，應當返回target在列表中的順序。此時應該滿足left > right, 且left = right+1

因此若target不在列表中，target在列表中有三種情況：

1.當target比列表的最左邊的值還小：

此時當left = right時，此時nums[mid]位于最左邊第一個元素，還大于target，應該right = mid-1最標為-1，則此時target應該放到第一位，滿足left。

2. 當target位于列表中間：

此時滿足left = right ，若nums[mid] <?target，即此時nums[mid]位于target相鄰的左邊！接下來需要進入if條件left = mid +1，則left此時即為target的位置；若nums[mid] < target，則此時nums[mid] >?target，即此時nums[mid]位于target相鄰的右邊！此時mid的位置即為target的位置，index（target） = left

3. 當target比列表的最左邊的值還大：

此時nums[mid]位于最右邊的元素，即target比列表所有元素都大，index（target） = mid = left = len（nums）-1

為防止棧溢出，可以將mid = (left+ right) // 2 寫成mid = left +?(right?- left) //2??更好。

?