Search Insert Position
Find the index of target in a sorted array, or the index where it would be inserted to maintain order.
2 min read
binary-search
Problem#
Sorted array nums. Return the index of target if present, otherwise the index where it would be inserted.
Examples#
nums = [1,3,5,6], target = 5→2nums = [1,3,5,6], target = 2→1
Constraints#
1 <= n <= 10^4.
Approach#
Lower-bound binary search.
Solution#
class Solution {public: int searchInsert(vector<int>& nums, int target) { int lo = 0, hi = nums.size(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < target) lo = mid + 1; else hi = mid; } return lo; }};func searchInsert(nums []int, target int) int { lo, hi := 0, len(nums) for lo < hi { mid := lo + (hi-lo)/2 if nums[mid] < target { lo = mid + 1 } else { hi = mid } } return lo}from bisect import bisect_leftfrom typing import List
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: return bisect_left(nums, target)function searchInsert(nums, target) { let lo = 0, hi = nums.length; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (nums[mid] < target) lo = mid + 1; else hi = mid; } return lo;}class Solution { public int searchInsert(int[] nums, int target) { int lo = 0, hi = nums.length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < target) lo = mid + 1; else hi = mid; } return lo; }}function searchInsert(nums: number[], target: number): number { let lo = 0, hi = nums.length; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (nums[mid] < target) lo = mid + 1; else hi = mid; } return lo;}Editorial#
Standard lower_bound template: hi = n (exclusive upper bound), lo < hi, lo = mid + 1 if smaller, hi = mid if at-least. Final lo is the first index ≥ target — the insert position.
Complexity#
- Time: O(log n).
- Space: O(1).
Concept revision#
Related#