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.
low
pointer will indicate the correct insertion point by the end of the search.#include <vector>
#include <iostream>
class Solution {
public:
int searchInsert(std::vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return low; // low is the insertion point
}
};
int main() {
Solution solution;
std::vector<int> nums = {1, 3, 5, 6};
int target = 5;
std::cout << "Index: " << solution.searchInsert(nums, target) << std::endl; // Output: 2
target = 2;
std::cout << "Index: " << solution.searchInsert(nums, target) << std::endl; // Output: 1
target = 7;
std::cout << "Index: " << solution.searchInsert(nums, target) << std::endl; // Output: 4
target = 0;
std::cout << "Index: " << solution.searchInsert(nums, target) << std::endl; // Output: 0
return 0;
}
n
is the number of elements in the array. This is because binary search is a logarithmic time search algorithm.This implementation ensures that we efficiently find the correct target index or insertion point in logarithmic time.
Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?