Binary Search

Binary Search

35. Search Insert Position: 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.

Approach & Solution:

This problem can be solved using lower_bound. Here are common variations of binary search, suitable for searching in the integer domain:

1. First >= x: lower_bound(x)
2. First > x: lower_bound(x + 1)
3. Last <= x: lower_bound(x + 1) - 1
4. Last < x: lower_bound(x) - 1

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

Complexity Analysis:

• Time Complexity: O(log n), as the search range is halved in each step.
• Space Complexity: O(1), only constant extra space is used.

34. Find First and Last Position of Element in Sorted Array: leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.

Approach & Solution:

Use lower_bound to find the boundaries.

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

Complexity Analysis:

• Time Complexity: O(log n), each binary search takes O(log n) time.
• Space Complexity: O(1), only constant extra space is used.