#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;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyByZWN1cnNpdmUgbW9kaWZpZWQgYmluYXJ5IHNlYXJjaAppbnQgaW5zZXJ0UG9zKHZlY3RvcjxpbnQ+ICZudW1zLCBpbnQgbG93LCBpbnQgaGlnaCwgaW50IHRhcmdldCl7CiAgICAvL2Jhc2UgY2FzZSB3aXRoIDEgZWxlbWVudAogICAgaWYobG93ID09IGhpZ2gpewogICAgICAgIGlmKG51bXNbbG93XSA8IHRhcmdldCl7CiAgICAgICAgICAgIHJldHVybiBsb3cgKyAxOwogICAgICAgIH1lbHNlewogICAgICAgICAgICByZXR1cm4gbG93OwogICAgICAgIH0KICAgIH0KICAgIC8vYmFzZSBjYXNlIHdpdGggMiBlbGVtZW50cwogICAgaWYobG93ID09IGhpZ2ggLSAxKXsKICAgICAgICBpZihudW1zW2hpZ2hdIDwgdGFyZ2V0KXsKICAgICAgICAgICAgcmV0dXJuIGhpZ2ggKyAxOwogICAgICAgIH1lbHNlIGlmKHRhcmdldCA8PSBudW1zW2xvd10pewogICAgICAgICAgICByZXR1cm4gbG93OwogICAgICAgIH1lbHNlewogICAgICAgICAgICByZXR1cm4gaGlnaDsKICAgICAgICB9CiAgICB9CiAgICAvL3JlY3Vyc2l2ZSBjYWxsIGJhc2VkIG9uIHRoZSBpbmRleCAKICAgIGludCBtaWQgPSBsb3cgKyAoKGhpZ2ggLSBsb3cpID4+IDEpOwogICAgaWYobnVtc1ttaWRdID09IHRhcmdldCl7CiAgICAgICAgcmV0dXJuIG1pZDsKICAgIH1lbHNlIGlmKG51bXNbbWlkXSA8IHRhcmdldCAmJiBudW1zW21pZCArIDFdID4gdGFyZ2V0KXsKICAgICAgICByZXR1cm4gbWlkICsgMTsKICAgIH1lbHNlIGlmKG51bXNbbWlkXSA+IHRhcmdldCl7CiAgICAgICAgcmV0dXJuIGluc2VydFBvcyhudW1zLCBsb3csIG1pZCAtIDEsIHRhcmdldCk7CiAgICB9ZWxzZXsKICAgICAgICByZXR1cm4gaW5zZXJ0UG9zKG51bXMsIG1pZCArIDEsIGhpZ2gsIHRhcmdldCk7CiAgICB9Cn0KCmludCBzZWFyY2hJbnNlcnQodmVjdG9yPGludD4mIG51bXMsIGludCB0YXJnZXQpIHsKICAgIHJldHVybiBpbnNlcnRQb3MobnVtcywgMCwgbnVtcy5zaXplKCktMSwgdGFyZ2V0KTsKfQoKaW50IG1haW4oKSB7CglpbnQgbXlpbnRzW10gPSB7MTAsIDIwLCAzMCwgNDAsIDUwLCA2MCwgNzAsIDgwfTsKCXZlY3RvcjxpbnQ+IHYobXlpbnRzLCBteWludHMrOCk7ICAgICAgICAgICAvLyAxMCAyMCAzMCAzMCAyMCAxMCAxMCAyMAoJc29ydCh2LmJlZ2luKCksIHYuZW5kKCkpOyAgICAgICAgICAgICAgICAvLyAxMCAxMCAxMCAyMCAyMCAyMCAzMCAzMAoJY291dCA8PCBzZWFyY2hJbnNlcnQodiwgMzUpIDw8IGVuZGw7CiAJcmV0dXJuIDA7Cn0=