Find the index where a target belongs in a sorted array, or the index of the target if it already exists.
Problem
You are 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 inserted in order while keeping the array sorted.
Your solution should be efficient enough to handle large arrays, so a linear scan is not ideal when the array is already sorted.
Input
- A sorted array of integers in strictly increasing order
- An integer target
Task
Determine the position at which the target appears or should be inserted.
Notes
- The array is sorted in ascending order.
- There are no duplicate values in the array.
- The returned position uses 0-based indexing.
Input Format
nums: a sorted array of distinct integerstarget: an integer to locate or insert
Output Format
- Return a single integer: the index of
targetif present, otherwise the insertion position that preserves sorted order.
Constraints
0 <= nums.lengthnumsis sorted in strictly increasing order- Elements and target are integers
- Use 0-based indexing
Example 1
Input
nums = [1, 3, 5, 6], target = 5
Output
2
Explanation
The target exists in the array at index 2.
Example 2
Input
nums = [1, 3, 5, 6], target = 2
Output
1
Explanation
The target is not present. It should be inserted between 1 and 3, which is index 1.
Show 1 more example
Example 3
Input
nums = [1, 3, 5, 6], target = 7
Output
4
Explanation
The target is greater than every element, so it would be inserted at the end.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.