35. Search Insert Position - leetcode - python - easy

 

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

class Solution:

    def searchInsert(self, nums: list[int], target: int) -> int:

        left, right = 0, len(nums) - 1

        while left <= right:

            mid = (left + right) // 2

            if nums[mid] < target:

                left = mid + 1

            elif nums[mid] > target:

                right = mid - 1

            else:

                return mid

        return left

Initialize left and right pointers. Find mid index and compare nums[mid] with target: If nums[mid] < target → search right half If nums[mid] > target → search left half If equal → return mid If not found → left is the correct insert position.