fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // recursive modified binary search
  5. int insertPos(vector<int> &nums, int low, int high, int target){
  6. //base case with 1 element
  7. if(low == high){
  8. if(nums[low] < target){
  9. return low + 1;
  10. }else{
  11. return low;
  12. }
  13. }
  14. //base case with 2 elements
  15. if(low == high - 1){
  16. if(nums[high] < target){
  17. return high + 1;
  18. }else if(target <= nums[low]){
  19. return low;
  20. }else{
  21. return high;
  22. }
  23. }
  24. //recursive call based on the index
  25. int mid = low + ((high - low) >> 1);
  26. if(nums[mid] == target){
  27. return mid;
  28. }else if(nums[mid] < target && nums[mid + 1] > target){
  29. return mid + 1;
  30. }else if(nums[mid] > target){
  31. return insertPos(nums, low, mid - 1, target);
  32. }else{
  33. return insertPos(nums, mid + 1, high, target);
  34. }
  35. }
  36.  
  37. int searchInsert(vector<int>& nums, int target) {
  38. return insertPos(nums, 0, nums.size()-1, target);
  39. }
  40.  
  41. int main() {
  42. int myints[] = {10, 20, 30, 40, 50, 60, 70, 80};
  43. vector<int> v(myints, myints+8); // 10 20 30 30 20 10 10 20
  44. sort(v.begin(), v.end()); // 10 10 10 20 20 20 30 30
  45. cout << searchInsert(v, 35) << endl;
  46. return 0;
  47. }
Success #stdin #stdout 0s 16064KB
stdin
Standard input is empty
stdout
3