If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
1. Overview
In this post, we will see how to search an element in sorted and rotated array.
2. Introduction to Problem Statement
We are given an sorted and rotated array as below:
|
|
int arr[]={16,19,21,25,3,5,8,10}; |
Our goal is search an element in above array in o(log n) time complexity.
Input: arr[] = {16,19,21,25,3,5,8,10}, element = 5
Output: Found at index 5.
Input: arr[] = {16,19,21,25,3,5,8,10}, element = 11
Output: -1 (Not found).
3. Using Binary Search Variant
We can use variant of binary search algorithm to solve above problem. We can use a property that we can divide array into two sorted sub arrays ({16,19,21,25},{3,5,8,10} ), although you do not need to find pivot point(Elements start decreasing).
Algorithm:
- Compute mid i.e low+high/2.
- Check if a[mid…high] is sorted
- If number lies between the range, set low=mid+1.
- If number does not lie in the range, set high=mid-1.
- Check if a[low..mid] is sorted.
- If number lies between the range, set high=mid-1.
- If number does not lie in the range, set low=mid+1.
Lets understand this with the help of example.
Steps involved to search 5 in above array:
- Compute mid i.e. 3 (0+7/2)
- a[mid](25) > a[high](10) && 5 < a[low](16) && 5< a[mid] (25), so number (5) lies in right part, so low will become mid+1.
- In next iteration, a[mid]==5, so we can return it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
public class SearchElementSortedAndRotatedArrayMain { public static void main(String[] args) { int arr[]={16,19,21,25,3,5,8,10}; System.out.println("Index of element 5 : "+findElementRotatedSortedArray(arr,0,arr.length-1,5)); } public static int findElementRotatedSortedArray(int[] arr,int low,int high,int number) { int mid; while(low<=high) { mid=low + ((high - low) / 2);; if(arr[mid]==number) { return mid; } if(arr[mid]<=arr[high]) { // Right part is sorted if(number > arr[mid] && number <=arr[high]) { low=mid+1; } else { high=mid-1; } } else { // Left part is sorted if(arr[low]<=number && number < arr[mid]) { high=mid-1; } else { low=mid+1; } } } return -1; } } |
When you run above program, you will get below output:
We can find element in the array using linear search, but time complexity is o(n).
Steps to find element in the array using linear search:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class LinearSearch { // This method returns index of element x in arr[] static int linearSearch(int arr[], int x) { for (int i = 0; i < arr.length; i++) { // Return the index of the element if the element // is found if (arr[i] == x) return i; } // return -1 if the element is not found return -1; } public static void main(String[] args) { int arr[]={16, 19, 21, 25, 3, 5, 8, 10}; int x = 5; int index = linearSearch(arr, x); if (index == -1) System.out.println("Element is not found in the array"); else System.out.println("Element found at position " + index); } } |
In this article, we have coverted two ways to search element in sorted and and rotated array. Linear search takes O(n) time and not optimal while binary search takes o(logn) and is faster than linear search.
