Practice/Meta/Leetcode 35. Search Insert Position

Leetcode 35. Search Insert Position

CodingOptional

Problem

You are given a sorted array of unique integers and a target value. Your task is to find and return the index position of the target value in the array. If the target does not exist in the array, return the index where it would need to be inserted to maintain the sorted order.

The solution must run in O(log n) time complexity, which means you should use a binary search approach rather than a linear scan.

Requirements

1. Return the index if the target value exists in the array
2. Return the insertion position if the target value does not exist
3. The returned index must maintain the sorted order of the array
4. Implement an algorithm with O(log n) time complexity
5. All integers in the array are distinct (no duplicates)

Constraints

• 1 ≤ nums.length ≤ 104
• -104 ≤ nums[i] ≤ 104
• nums contains distinct values sorted in ascending order
• -104 ≤ target ≤ 104
• Time complexity must be O(log n)

Examples

Example 1:

Input: nums = [1, 3, 5, 6], target = 5 Output: 2 Explanation: The value 5 exists in the array at index 2.

Example 2:

Input: nums = [1, 3, 5, 6], target = 2 Output: 1 Explanation: The value 2 does not exist in the array. It should be inserted at index 1 to keep the array sorted: [1, 2, 3, 5, 6].

Example 3:

Input: nums = [1, 3, 5, 6], target = 7 Output: 4 Explanation: The value 7 is greater than all elements. It should be inserted at the end (index 4).

Example 4:

Input: nums = [1, 3, 5, 6], target = 0 Output: 0 Explanation: The value 0 is less than all elements. It should be inserted at the beginning (index 0).