LeetCode: 35 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: nums = [1,3,5,6], target = 5
Output: 2

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

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

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

问题

给定一个排序的整数数组和一个目标值 target，如果目标值存在于数组中，返回它的索引。如果不存在，返回它应该被插入的位置。你必须编写一个 O(log n) 复杂度的算法。

例子

输入: nums = [1,3,5,6], target = 5
输出: 2

输入: nums = [1,3,5,6], target = 2
输出: 1

输入: nums = [1,3,5,6], target = 7
输出: 4

输入: nums = [1,3,5,6], target = 0
输出: 0

Iterative Solution

Approach: Binary Search / 二分查找

To find the target or the insertion point, we can use binary search since the array is sorted. Binary search has a time complexity of O(log n), which meets the problem requirements.

Approach Explanation / 方法解释

Binary Search: Use two pointers left and right to define the search range. Calculate the middle element and compare it to the target.
Move Pointers: If the middle element is less than the target, move left to mid + 1. If it’s greater than the target, move right to mid - 1.
Insert Position: When left exceeds right, the value of left will be the insertion position.

Iterative Algorithm / 迭代算法

Initialize left = 0 and right = len(nums) - 1.
Perform binary search:
- If nums[mid] == target, return mid.
- If nums[mid] < target, move left to mid + 1.
- If nums[mid] > target, move right to mid - 1.
Return left as the insert position.

Iterative Implementation / 迭代实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        # Perform binary search
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        # Return the insert position
        return left

Iterative Solution Explanation / 迭代解决方案解释

Initialize Left and Right Pointers / 初始化左右指针
```
left, right = 0, len(nums) - 1
```
- English: We initialize left at the start of the array and right at the end of the array.
- Chinese: 我们将 left 初始化为数组的起始位置，right 初始化为数组的末尾位置。
Perform Binary Search / 执行二分查找
```
while left <= right:
   mid = (left + right) // 2
   if nums[mid] == target:
       return mid
   elif nums[mid] < target:
       left = mid + 1
   else:
       right = mid - 1
```
- English: We calculate the middle element mid and compare it to the target. Depending on the comparison result, we adjust the left or right pointer.
- Chinese: 我们计算中间元素 mid 并将其与目标值进行比较。根据比较结果，调整 left 或 right 指针。
Return Insert Position / 返回插入位置
```
return left
```
- English: If the target is not found, left will represent the insertion position.
- Chinese: 如果没有找到目标值，left 将表示插入位置。

Recursive Solution

Approach: Recursive Binary Search / 递归二分查找

We can also implement the binary search recursively by breaking the array down into smaller parts until we find the target or the insertion point.

Recursive Algorithm / 递归算法

Use left and right to define the search range.
If left exceeds right, return left as the insert position.
Calculate the middle index mid and compare nums[mid] to the target:
- If nums[mid] == target, return mid.
- If nums[mid] < target, search in the right half (left = mid + 1).
- If nums[mid] > target, search in the left half (right = mid - 1).

Recursive Implementation / 递归实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def binarySearch(left, right):
            if left > right:
                return left
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                return binarySearch(mid + 1, right)
            else:
                return binarySearch(left, mid - 1)

        return binarySearch(0, len(nums) - 1)

Recursive Solution Explanation / 递归解决方案解释

Base Case: If Left Exceeds Right / 基本情况：如果左指针超过右指针
```
if left > right:
   return left
```
- English: If left exceeds right, it means the target is not in the array, so return left as the insertion point.
- Chinese: 如果 left 超过 right，说明目标值不在数组中，因此返回 left 作为插入点。
Recursive Binary Search / 递归二分查找
```
mid = (left + right) // 2
if nums[mid] == target:
   return mid
elif nums[mid] < target:
   return binarySearch(mid + 1, right)
else:
   return binarySearch(left, mid - 1)
```
- English: We calculate mid, compare it to the target, and recursively search either the left or right half.
- Chinese: 我们计算 mid，将其与目标值进行比较，并递归搜索左半部分或右半部分。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(log n), where n is the number of elements in the array. Both the iterative and recursive approaches use binary search.
Space Complexity / 空间复杂度:
- Iterative Solution: O(1), since no extra space is used.
- Recursive Solution: O(log n), due to the recursion stack in the worst case.

Key Concept / 关键概念

Binary Search / 二分查找: Binary search is an efficient way to find an element in a sorted array with O(log n) time complexity. It repeatedly divides the search space in half.
Recursion / 递归: The recursive approach divides the problem into smaller subproblems until the base case is reached.

Summary / 总结

English: We can solve the problem of finding the target or its insertion position using binary search. Both iterative and recursive solutions provide O(log n) time complexity.
Chinese: 我们可以通过二分查找解决找到目标或其插入位置的问题。迭代和递归解决方案都提供 O(log n) 的时间复杂度。

Tips / 提示

English: Make sure to handle the edge cases where the target is smaller than the first element or larger than the last element.
Chinese: 确保处理目标值小于第一个元素或大于最后一个元素的边缘情况。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice binary search problems to strengthen your understanding of divide-and-conquer algorithms.
Chinese: 练习二分查找问题，以加强对分治算法的理解。

LeetCode #35: Search Insert Position | Binary Search by Algo Engine

Post Views: 11

CODEBITWAVE