fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int pivot_search(int A[],int low, int high)
  5. {
  6.     if(low > high) return -1;
  7.  
  8.     int mid;
  9.     mid = (low+high)/2;
  10.     if(high-low+1 == 2 && A[low] > A[high]) return low;
  11.     if( A[mid-1] < A[mid] && A[mid+1] < A[mid]) return mid;
  12.  
  13.     if(A[mid] < A[low]){
  14.         return pivot_search(A,low,mid-1);
  15.     } else {
  16.         return pivot_search(A,mid+1,high);
  17.     }
  18. }
  19.  
  20. int binary(int A[], int low, int high, int x)
  21. {
  22.     if(low > high) return -1;
  23.     int mid = (low+high)/2;
  24.  
  25.     if(A[mid] == x) return mid;
  26.  
  27.     if(A[mid] < x){
  28.         return binary(A,mid+1, high,x);
  29.     } else {
  30.         return binary(A,low, mid-1, x);
  31.     }
  32. }
  33. int search(int A[], int n, int target) {
  34.  
  35.         int pivot;
  36.         pivot = pivot_search(A,0,n-1);
  37.         if(pivot == -1) pivot = n-1;
  38.        //cout << pivot << endl;
  39.         if(target >= A[0]){
  40.             return binary(A,0,pivot,target);
  41.         } else {
  42.             return binary(A,pivot+1,n-1, target);
  43.         }
  44. }
  45. int main() {
  46. 	int n;
  47. 	cin >> n;
  48.  
  49. 	int A[n];
  50. 	for (int i = 0; i < n; i++) cin >> A[i];
  51.  
  52. 	int tar;
  53. 	cin >> tar;
  54.  
  55. 	cout << search(A,n,tar);
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
2
1 2 
1
stdout
copy 
Standard output is empty
https://ideone.com/JsW1JT
language:
C++ (gcc 8.3)
created:
10 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!