35. Search Insert Position

Problem Statement

link: https://leetcode.com/problems/search-insert-position/ https://leetcode.cn/problems/search-insert-position/

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:

Input: [1,3,5,6] Output: 5

Input: [1,3,5,6] Output: 2

Input: [1,3,5,6] Output: 7

Solution Approach

The problem can be solved by using a binary search approach to locate the position of the target value in the sorted list.

Algorithm

1. Implement a binary search by initializing pointers l and r at the start and end of the list, then compute the middle index mid to compare the element at mid with the target.
2. Adjust pointers based on the comparison, and if the target isn’t found, return the position l where it would be inserted.

Implement

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

    
    

Twitter  facebook  Email