Search Insert Position
LeetCode #35 · Easy · Binary Search · C++ solution with worked-out approach and complexity analysis.
Approach
Binary Search
Use binary search to find the target or the position where it should be inserted. Maintain left and right pointers, calculate mid, and adjust based on comparison.
Time
O(log n)
Space
O(1)
Problem description(from LeetCode)
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.
Examples
Example 1
- Input:
- nums = [1,3,5,6], target = 5
- Output:
- 2
Constraints
- •1 <= nums.length <= 10^4
- •-10^4 <= nums[i] <= 10^4
- •nums contains distinct values sorted in ascending order.
- •-10^4 <= target <= 10^4
C++ Solution
solution.cpp
class Solution {
public:
int searchInsert(vector<int> &nums, int target) {
int left = 0, right = nums.size();
int index;
while (left < right) {
index = (left + right) / 2;
int node = nums[index];
if (node == target) return index;
if (target > node) {
left = index + 1;
} else {
right = index;
}
}
return nums[index] < target ? index + 1 : index;
}
};