📌 Problem

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.

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

Example 4:

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

Example 5:

Input: nums = [1], target = 0
Output: 0

Constraints:

• $1$ <= nums.length <= $10^4$
• $-10^4$ <= nums[i] <= $10^4$
• nums contains distinct values sorted in ascending order.
• $-10^4$ <= target <= $10^4$

---

📝 Solution

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        
        # nums(Ascending order) 
        left=0
        right=len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]>target: # Search to left
                right=mid-1
            elif nums[mid]<target: # Search to right 
                left=mid+1   
            else: # Correct
                return mid
        # Incorrect
        return left 

• Time complexity : $O(logn)$

• Binary Search 를 이용하여 target 이 있으면 mid , target 이 없는 경우 left 를 리턴한다.