fork download
copy 
  1. // C++ program to search an element in sorted and rotated 
  2. // array using binary search
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. int search(vector<int>& arr, int key) {
  9.  
  10.     // Initialize two pointers, lo and hi, at the start
  11.     // and end of the array
  12.     int lo = 0, hi = arr.size() - 1;
  13.  
  14.     while (lo <= hi) {
  15.         int mid = lo + (hi - lo) / 2;
  16.  
  17.         // If key found, return the index
  18.         if (arr[mid] == key)
  19.             return mid;
  20.  
  21.         // If Left half is sorted
  22.         if (arr[mid] >key) {
  23.  
  24.             // If the key lies within this sorted half,
  25.             // move the hi pointer to mid - 1
  26.             if (key >= arr[lo] && key < arr[mid])
  27.                 hi = mid - 1;
  28.  
  29.             // Otherwise, move the lo pointer to mid + 1
  30.             else
  31.                 lo = mid + 1;
  32.         }
  33.  
  34.         // If Right half is sorted
  35.         else {
  36.  
  37.             // If the key lies within this sorted half,
  38.             // move the lo pointer to mid + 1
  39.             if (key > arr[mid] && key <= arr[hi])
  40.                 lo = mid + 1;
  41.  
  42.             // Otherwise, move the hi pointer to mid - 1
  43.             else
  44.                 hi = mid - 1;
  45.         }
  46.     }
  47.  
  48.   	// Key not found
  49.     return -1; 
  50. }
  51.  
  52. int main() {
  53.     vector<int> arr1 = {5, 6, 7, 8, 9, 10, 1, 2, 3};
  54.     int key1 = 3;
  55.     cout << search(arr1, key1) << endl;
  56.  
  57.     return 0;
  58. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
9
stdout
copy 
8
https://ideone.com/JlFU3A
language:
C++ (gcc 8.3)
created:
6 days 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!