35. Search Insert Position (Leetcode || Java || Easy)

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.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

SOLUTION:

class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;//defining range for binary search
int end = nums.length — 1;

while(start <= end){//applying binary search
int mid = start + (end — start)/2;

if(nums[mid] == target){//if target is in the array return its index that is mid
return mid;
}
else if(nums[mid] > target){
end = mid — 1;
}else{
start = mid + 1;
}
}

return start;//if target is not in array then start will provide its correct index
}
}

TIME COMPLEXITY :- O(log(n))

SPACE COMPLEXITY :- O(1)

Thank you for reading. If you have any queries please let me know in the comment section.