fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/TbFRxX
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!