// Using While Loop
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int start = 0, end = nums.size()-1;
        while(start<=end)    {
            int mid = (start+end)/2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target)    
                start = mid+1;
            else 
                end = mid-1;
        }
        return start;
    }
};


//Using Recursion
class Solution {
public:
    int BinSearch(vector<int>nums,int start, int end, int target) {
        if(end < start) {
            return start;
        }
        int mid = (start + end) / 2;
        if(nums[mid] == target) {
            return mid;
        }
        else if(nums[mid] < target) {
            return BinSearch(nums, mid+1, end, target);   
        }
        else {
            return BinSearch(nums, start, mid-1,target);
        }
    }
    int searchInsert(vector<int>& nums, int target) {
        return BinSearch(nums,0,nums.size()-1,target);  
    }
};