fork download 
  1. #include <stdio.h>
  2.  
  3. // Function to find an element x in a circularly sorted array
  4. int circularArraySearch(int A[], int n, int x)
  5. {
  6.     // search space is A[low..high]
  7.     int low = 0, high = n - 1;
  8.  
  9.     // iterate till search space contains at-least one element
  10.     while (low <= high)
  11.     {
  12.         // find the mid value in the search space and
  13.         // compares it with target value
  14.         int mid = (low + high)/2;
  15.  
  16.         // if target is found, return its index
  17.         if (x == A[mid])
  18.             return mid;
  19.  
  20.         // if right half (A[mid..high]) is sorted and mid is not
  21.         // the target element
  22.         if (A[mid] <= A[high])
  23.         {
  24.             // compare target with A[mid] and A[high] to know
  25.             // if it lies in A[mid..high] or not
  26.             if (x > A[mid] && x <= A[high])
  27.                 low = mid + 1;    // go searching in right sorted half
  28.             else
  29.                 high = mid - 1;    // go searching left
  30.         }
  31.  
  32.         // if left half (A[low..mid]) is sorted and mid is not
  33.         // the target element
  34.         else
  35.         {
  36.             // compare target with A[low] and A[mid] to know
  37.             // if it lies in A[low..mid] or not
  38.             if (x >= A[low] && x < A[mid])
  39.                 high = mid - 1;    // go searching in left sorted half
  40.             else
  41.                 low = mid + 1;    // go searching right
  42.         }
  43.     }
  44.  
  45.     // target not found or invalid input
  46.     return -1;
  47. }
  48.  
  49. // main function
  50. int main(void)
  51. {
  52.     int A[] = {9, 10, 2, 5, 6, 8};
  53.     int target = 5;
  54.  
  55.     int n = sizeof(A)/sizeof(A[0]);
  56.     int index = circularArraySearch(A, n, target);
  57.  
  58.     if (index != -1)
  59.         printf("Element found at index %d", index);
  60.     else
  61.         printf("Element not found in the array");
  62.  
  63.     return 0;
  64. }
Success #stdin #stdout 0s 4288KB
comments (?)
stdin 
Standard input is empty
stdout 
Element found at index 3
https://ideone.com/nS3jmS
Search an element in a circular sorted array
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

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!