C program to search an element in a sorted and rotated array

In this blog post, we learn how to write a C program to search an element in a sorted and rotated array? So here we will write a C program to search an element in a sorted and rotated array.

Suppose an array ( ‘arr’ ) sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2 ).

Now here task to search the given target in a rotating sorted array. If the target element found in the array, return its index, otherwise return -1.

Note: Input array must be sorted in ascending order.

Example,

Input: int arr[] = {4, 5, 6, 7, 0, 1, 2, 3};
Target Element = 4

Output: 0

Explanation: Target 4 is found at index 0 in arr.

Logic to search an element in a sorted and rotated array

The interesting property of a sorted and rotated array is that when you divide it into two halves, at least one of the two halves will always be sorted. Suppose an input array is {1,2,3,4,5,6,7,8,9} at some of points it becomes {4,5,6,7,8,9,1,2,3}.

Array at some point during rotation = {4,5,6,7,8,9,1,2,3}

number of elements  = 9

mid index = (lowIndex + highIndex)/2 = (0+8)/2 =4


{4,5,6,7,8,9,1,2,3}
         ^
 left   mid  right

You can see right sub-array is not sorted while the left sub-array is sorted. So in any point of rotation one of the half(sub-array) must be sorted.

Now let’s see the steps which will use to find the key elements in the given sorted rotating array.

1. Find the middle point of the given sorted array.

2. Find the half-sorted array by comparing the start and end elements of each half.

3. Once we find which half is sorted we can see if the key is present in that half or not by simple comparison with the extremes.

4. If the key is not present in the first sorted half then we will check another second half.

If you want to learn more about the C language, you can check this course, Free Trial Available.

#include <stdio.h>

//Calculate array size
#define ARRAY_SIZE(arr)  sizeof(arr)/sizeof(arr[0])


// Returns index of target in arr[l..h] if
// target is present, otherwise returns -1
int SearchTargetValue(int arr[], int lowIndex, int highIndex, int target)
{
    //target not present
    if (lowIndex > highIndex)
        return -1;

    int mid = (lowIndex + highIndex) / 2;

    //target found
    if (arr[mid] == target)
        return mid;

    // If left part is sorted (arr[lowIndex...mid] is sorted).
    if (arr[lowIndex] <= arr[mid])
    {
        /* As this subarray is sorted, we can quickly
        check if target lies in half or other half */
        if (target >= arr[lowIndex] && target <= arr[mid])
            return SearchTargetValue(arr, lowIndex, mid - 1, target);

        /*If target not lies in first half subarray,
        Divide other half into two subarrays,
        such that we can quickly check if target lies
        in other half */
        return SearchTargetValue(arr, mid + 1, highIndex, target);
    }

    /* If arr[lowIndex..mid] first subarray is not sorted, then arr[mid... highIndex]
    must be sorted subarray */
    if (target >= arr[mid] && target <= arr[highIndex])
        return SearchTargetValue(arr, mid + 1, highIndex, target);

    return SearchTargetValue(arr, lowIndex, mid - 1, target);
}

int main()
{
    //array must be sorted
    int arr[] = {8, 11, 13, 15, 1, 4, 6};

    int targetElement = 1;

    //get array size
    int arr_size = ARRAY_SIZE(arr);

    const int indexTarget = SearchTargetValue(arr, 0, arr_size-1,targetElement);

    if(indexTarget != -1)
    {
        //rearrange elements
        printf("Target Element Index = %d\n",indexTarget);
    }
    else
    {
        printf("Element not found in array\n");
    }

    return 0;
}

C program to search an element in a sorted and rotated array

Logic to search an element in a sorted and rotated array

Recommended Articles for you: