#include <bits/stdc++.h>
using namespace std;

// recursive modified binary search
int insertPos(vector<int> &nums, int low, int high, int target){
    //base case with 1 element
    if(low == high){
        if(nums[low] < target){
            return low + 1;
        }else{
            return low;
        }
    }
    //base case with 2 elements
    if(low == high - 1){
        if(nums[high] < target){
            return high + 1;
        }else if(target <= nums[low]){
            return low;
        }else{
            return high;
        }
    }
    //recursive call based on the index 
    int mid = low + ((high - low) >> 1);
    if(nums[mid] == target){
        return mid;
    }else if(nums[mid] < target && nums[mid + 1] > target){
        return mid + 1;
    }else if(nums[mid] > target){
        return insertPos(nums, low, mid - 1, target);
    }else{
        return insertPos(nums, mid + 1, high, target);
    }
}

int searchInsert(vector<int>& nums, int target) {
    return insertPos(nums, 0, nums.size()-1, target);
}

int main() {
	int myints[] = {10, 20, 30, 40, 50, 60, 70, 80};
	vector<int> v(myints, myints+8);           // 10 20 30 30 20 10 10 20
	sort(v.begin(), v.end());                // 10 10 10 20 20 20 30 30
	cout << searchInsert(v, 35) << endl;
 	return 0;
}