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 rightYou 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;
}
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- C program to rearrange array such that elements at even positions are greater than odd.
- C program to remove duplicates from sorted array
- C program to find the Median of two sorted arrays of different sizes.
- C Program to find first and last position of the element in a sorted array
- Write C program to find the missing number in a given integer array of 1 to n
- C program to find the most popular element in an array
- Find the largest and smallest element in an array using C programming.
- C program to find even occurring elements in an array of limited range
- Find sum of all sub-array of a given array.
- C program to segregate even and odd numbers
- Find an element in array such that sum of left array is equal to sum of right array.
- C Program to find the count of even and odd elements in the array.
- Write C program to find the sum of array elements.
- C program to find odd occurring elements in an array of limited range
- Find the sum of array elements using recursion
- C Program to reverse the elements of an array
- C Program to find the maximum and minimum element in the array
- Calculate size of an array in without using sizeof in C
- How to create a dynamic array in C?
One comment