Search Circular Array - C++ Solution

1. Introduction

In this blog post, we will delve into an interesting variant of binary search. We will tackle the problem of searching for a target element in a circularly sorted array, which is a common scenario in rotating buffers and circular lists.

Problem

Given a circularly sorted integer array without duplicates, the task is to find the index of a target element. If the target exists, return its index; if not, return -1. The array is assumed to be sorted in an increasing order but rotated some number of times in an anti-clockwise direction.

2. Solution Steps

1. Implement a modified binary search that accounts for the circular nature of the array.

2. Determine the middle element and compare it with the target.

3. Based on the comparison, decide whether to search in the left half or the right half of the array.

4. Adjust the search algorithm to handle the cases where the target might be in the rotated part of the array.

5. Continue the process until the target is found or the search space is exhausted.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to search in a circularly sorted array
int searchInCircularArray(const vector<int>& nums, int target) {
    int low = 0, high = nums.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if mid is the target
        if (nums[mid] == target) {
            return mid;
        }

        // Check if the left half is sorted
        if (nums[low] <= nums[mid]) {
            if (target >= nums[low] && target < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // The right half must be sorted
        else {
            if (target > nums[mid] && target <= nums[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }

    return -1; // Target not found
}

int main() {
    vector<int> nums = {8, 9, 10, 2, 5, 6};
    int target = 10;
    cout << "Index of target " << target << ": " << searchInCircularArray(nums, target) << endl;
    return 0;
}

Output:

Index of target 10: 2

Explanation:

The function searchInCircularArray implements a modified binary search to handle circularly sorted arrays. It determines whether to search in the left or right half by identifying the sorted part of the array. For instance, in the array [8, 9, 10, 2, 5, 6] with target 10, the target is found at the 3rd position (index 2). The algorithm efficiently handles cases where the array is rotated, ensuring logarithmic time complexity.