35 Search Insert Position

1. Description

Given a sorted array of distinct integer 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.

 

constraints :

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

2. Algorithms

To find index efficientyl with O(log n) time complexity, we need to use binary search algorithm(Because nums is sorted array.).

 

1. Initialize two pointer range_start, range_end. range_start is number with 0, range_end is length of nums.
2. Until range_start < range_end, range_start and range_end iterates.
   1. Initialize range_middle as quote of sum of range_start and range_end.
   2. Store the value of index range_middle in nums named value.
   3. If value is same with target, return range_middle.
   4. If value is smaller than target, update range_start as range_middle + 1
   5. If vslue is bigger than target, update range_end as range_middle
3. Out of loop, return range_start. because range_start stores final index of nums.

Time complexity is O(log n) which is time compleixty from binary search algorithms.

3. Codes

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        range_start = 0
        range_end = len(nums)
        while range_start < range_end : 
            range_middle = (range_end + range_start) // 2
            value = nums[range_middle] 
            
            if value == target : 
                return range_middle 
            elif value < target : 
                range_start = range_middle + 1
            else : 
                range_end = range_middle
        return range_start

4. Conclusion