Given a sorted integers and a target value, return the index if the target is found. If not, return the index where it should be inserted.
Example
Input:
nums = [1,3,5,5,6], target = 2
Output:
1
Input: nums = [1,2,3,5,6], target = 7 Output: 5
Solution
we can use binary search to find if the number exist in the given list. If so, return the index.
If not, we will do a modification of binary search in which we keep finding the index where the target should be and we return the index
public class Solution {
public int SearchInsert(int[] nums, int target)
{
int res = Array.BinarySearch(nums, target);
if (res < 0)
return BS(0, nums.Length, nums, target);
else
return res;
}
public int BS(int low, int high , int[] nums, int target)
{
if (low >= high)
return low;
int mid = (low + high) / 2;
if (nums[mid] > target)
return BS(low, mid, nums, target);
else
return BS(mid+1,high, nums, target);
}
}