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&nbsp;write an algorithm with&nbsp;O(log n) runtime complexity.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 104
	-104 &lt;= nums[i] &lt;= 104
	nums contains distinct values sorted in ascending order.
	-104 &lt;= target &lt;= 104


class Solution:
    def searchInsert(self, nums, target):
        for i, num in enumerate(nums):
            if num >= target:
                return i
        return len(nums)
class Solution {
    public int searchInsert(int[] nums, int target) {
        int start=0;
        int end=nums.length-1;
        int ans=0;
        while(start<=end){
            int mid=start+(end-start)/2;
            if(target<nums[mid]){
                end=mid-1;
            }
            if(target>nums[mid]){
                start=mid+1;
            }
            if(target==nums[mid]){
                return mid;
            }
        }
        return start; 
    }
}
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int ans=0;
        int size=nums.size();
        if(target>nums[size-1]){
            return nums.size();
        }
        for(int i=0;i<nums.size();i++){
            while(target>nums[i]){
                if(target==nums[i]){
                    return i; 
                    i++;
                }
                ans=i+1;
                i++;
            }
            
        }
        return ans;
    }
};
var searchInsert = function(nums, target) {
    let start=0;
    let end= nums.length-1;

    while(start <= end) {
        const mid = Math.trunc((start+end)/2);
        if(nums[mid] === target) {
            return mid;
        }
        if(nums[mid] < target) {
            start = mid+1;
        } else {
            end = mid-1
        }
        if(nums[end]< target){
          return end+1;
        }

        if(nums[start] > target){
          return start;
        }
    }
};
Search Insert Position