Question

How to search for an element in circular sorted integer array with C++

Answer 1

#include <iostream>

int searchCircularSortedArray(int arr[], int size, int element) {
    int low = 0, high = size - 1;
 
    while (low <= high) {
        int mid = (low + high) / 2;
 
        if (element == arr[mid]) {
            return mid;
        }
 
        if (arr[mid] <= arr[high]) {
            if (element > arr[mid] && element <= arr[high]) {
                low = mid + 1;  // search the right sorted half
            }
            else {
                high = mid - 1; // search the left side
            }
        }
        else {
            if (element >= arr[low] && element < arr[mid]) {
                high = mid - 1; // search the left sorted half
            }
            else {
                low = mid + 1; // search the right side
            }
        }
    }
 
    return -1;
}
 
int main()
{
    int array[] = {6, 9, 10, 13, 2, 3, 5, 6, 8};
    int element = 5;
 
    int size = sizeof(array) / sizeof(array[0]);
    int index = searchCircularSortedArray(array, size, element);
 
    if (index != -1) {
        std::cout << "index = " << index;
    }
    else {
        std::cout << "Element not found";
    }
 
    return 0;
}
    
    
    
    
/*
run:
     
index = 6

*/

 

70+ SQL courses for beginners and professionals