Search_Insert_Position.java

//Leetcode 35. Search Insert Position
//Question - https://leetcode.com/problems/search-insert-position/

/*Given a sorted array 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 may assume no duplicates in the array.
Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

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

Example 4:

Input: [1,3,5,6], 0
Output: 0
*/

classSolution {
publicintsearchInsert(int[] nums, inttarget) {
intindex = -1;
intlow = 0; inthigh = nums.length-1;
intmid = -1;
intresult = -1;

while(low<=high){
mid = low + (high-low)/2;

if(nums[mid]==target) returnmid; //if target is present

elseif(nums[mid]>target){ 
result = mid; //store the latest mid ==> this could be the first occurrence of least element greater than target
high = mid - 1; //push algorithm to left in hopes to find first occurrence of least element greater than target OR to find the target itself
 }
elselow = mid+1;
 }

//if the control is here the target value must not be in nums
if(result==-1) returnnums.length; //No element in nums was greater than target ==> the target is the greatest ==> needs to be added at the end
elsereturnresult;//correct position for target found

 }
}