Search an Element in A Sorted and Rotated Array in Java

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:

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.

Search an element in sorted and rotated array

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.


When you run above program, you will get below output:

Time Complexity: o(logn) as binary search takes log n comparison to find an element.
Space Complexity: o(1) as there is no extra space used here.

4. Using Linear Search

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:

  • Iterate over the array
  • In each iteration, if current element is equal to key, return the index.
  • Return -1, in case we don’t find element in the array.


Time Complexity: o(n) as we iterated over array once.
Space Complexity: o(1) as there is no extra space used here.

5. Conclusion

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.

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *