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.

In this post, we will see how to search an element in sorted and rotated array.

Problem:

You are given an sorted and rotated array as below:

If you note that array is sorted and rotated. You need to search an element in above array in o(log n) time complexity.

Solution:

You can search an element in above array using linear search but that will take o(n).
You can use variant of binary search algorithm to solve above problem. You can use a property that you 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 , low=mid+1.
    • If number does not lie in the range, high=mid-1.
  • Check if a[low..mid] is sorted.
    • If number lies between the range, high=mid-1..
    • If number does not lie in the range,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[high] (25), so number (5) lies  in right part, so low will become mid+1.
  • a[mid] ==5, so you can return it.

Java program to search an element in a sorted and rotated array :

Create a class named
SearchElementSortedAndRotatedArrayMain.java.

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

Add Comment