Table of contents
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.
Example: Input: nums = [1,3,5,6], target = 5 Output: 2
Question Link : Search Insert Position
Example :
Input: nums = [1,3,5,6], target = 2
Output: 1
Example :
Input: nums = [1,3,5,6], target = 7
Output: 4
You must write an algorithm with O(log n) runtime complexity.
Approach :
We'll use Binary search here, as the array is sorted.
Just one thing we should keep in mind that if no conditions of if block matches, then instead of returning -1, we need to return s(start index).
Code :
class Solution {
public int searchInsert(int[] nums, int target) {
int s = 0;
int e = nums.length - 1;
int ans = 0;
while(s <= e){
int mid = s + (e - s) / 2;
if(target == nums[mid]){
return mid;
}
if(target < nums[mid]){
e = mid - 1;
}
if(target > nums[mid]){
s = mid + 1;
}
ans = mid;
}
return s;
}
}