5/1 每日一題

 Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

#有點奇怪 O(log n) 只的是二分搜尋法,

以下超出時間限制,反而直接retunr nums.index(target) 才成功

class Solution:

    def searchInsert(self, nums, target):

        left, right = 0, len(nums)

       

        while left < right:

            mid = (left + right) // 2

           

            print(f"left={left}")

            print(f"right={right}")

            print(f"mid={mid}")

           

            print(f"target={target}, nums[mid]={nums[mid]}")

           

            if target <= nums[mid]:

                right = mid

                print(f"target<=nums[mid],目標位在左半邊,所以righ向左移到這次回圈的mid位置上")

            else:

                left = mid +1

                print(f"target>ums[mid],目標位在右半邊,將left改成mid+1")

           

           

        return print(f"索引值即為left={left}")

           

tes=Solution()

nums=[1,3,5,6]

tes.searchInsert(nums,6)  #輸出1

print("-"*30)

tes.searchInsert(nums,7)  #輸出4

print("-"*30)

num1=[1,3]      

tes.searchInsert(num1,1)  #輸出0

---------------

PS C:\Users\K\OneDrive\桌面\AUTOKI> & C:/Users/K/AppData/Local/Programs/Python/Python311/python.exe c:/Users/K/OneDrive/桌面/AUTOKI/tr.py left=0 right=4 mid=2 target=6, nums[mid]=5 target > nums[mid], 表示 目標位在右半邊, 將left改成mid+1 left=3 right=4 mid=3 target=6, nums[mid]=6 target小於等於nums[mid],表示目標位在左半邊,所以righ向左移動到這次回圈的mid位置上 索引值即為left=3 ------------------------------ left=0 right=4 mid=2 target=7, nums[mid]=5 target > nums[mid], 表示 目標位在右半邊, 將left改成mid+1 left=3 right=4 mid=3 target=7, nums[mid]=6 target > nums[mid], 表示 目標位在右半邊, 將left改成mid+1 索引值即為left=4 ------------------------------ left=0 right=2 mid=1 target=1, nums[mid]=3 target小於等於nums[mid],表示目標位在左半邊,所以righ向左移動到這次回圈的mid位置上 left=0 right=1 mid=0 target=1, nums[mid]=1 target小於等於nums[mid],表示目標位在左半邊,所以righ向左移動到這次回圈的mid位置上 索引值即為left=0 PS C:\Users\K\OneDrive\桌面\AUTOKI>