Search insert position
InfoEdge India LtdThe problem
Given a sorted array of nums consisting 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.
Input: nums = [1, 3, 5, 6], target = 5 Output: 2 Explanation: The target value 5 is found at index 2 in the sorted array. Hence, the function returns 2.
Input: nums = [1, 3, 5, 6], target = 2 Output: 1 Explanation: The target value 2 is not found in the array. However, it should be inserted at index 1 to maintain the sorted order of the array.
Input: nums = [1, 3, 5, 6], target = 7
- 1 <= nums.length <= 105
- -105 <= nums[i] <= 105
- nums contains distinct values sorted in ascending order.
- -105<= target <= 105
cpp
class Solution {
public:
int searchInsert(vector<int> &nums, int target) {
}
};java
class Solution {
public int searchInsert(int[] nums, int target) {
}
}python
class Solution:
def searchInsert(self, nums, target):javascript
class Solution {
searchInsert(nums, target) {
}
}csharp
public class Solution {
public int SearchInsert(int[] nums, int target) {
}
}go
func searchInsert(nums []int, target int) int {
//your code goes here
}Stuck? Show a way to structure it+
- 01Use half-open bounds
- 02Compare midpoint with target
- 03Keep candidate insertion boundary
- 04Return left after convergence
- 05Test endpoints
Reference answer
Then expect these follow-ups
Why is left the insertion position at termination?
Tests: correctness reasoning
How would duplicates change the requested index?
Tests: constraint adaptation
Hiring now
Get the InfoEdge India Ltd interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question