Question 12 : Search an element in rotated and sorted array

 You are given a sorted and rotated array as below::

int arr[]={16,19,21,25,3,5,8,10};

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

You can search an element in the above array using linear search but that will take o(n).
You can use a variant of the binary search algorithm to solve the above problem. You can use a property that you can divide the array into two sorted sub-arrays ({16,19,21,25},{3,5,8,10} ), although you do not need to find a 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.

Let's understand this with the help of an 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[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.:

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 the above program, you will get the below output::

Index of element 5 : 5

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.               

Share This

• Facebook
• Twitter
• Linkedin
• Pinterest