Home » Array » Binary Search » Interviews » Search element In Sorted Rotated Array in Java

Search element In Sorted Rotated Array in Java

in , , - on 02:12:00 - No comments

Search the element In Sorted Rotated Array in Java.

Given an array which is sorted in ascending order and is rotated, say for example
Example: original array [1,2,3,4,5,6,7] might become [3,4,5,6,7,1,2]
You are given a key to search. If key is found in the array return its index, otherwise return -1.

Note: You may assume no duplicate exists in the array, find an element in the rotated array in
O(log n) time.

Lets see sample input and output:

Algorithm 

Since the array is sorted and rotated, we can still use Binary Search to find the element present or not.

Example: {5, 6, 7, 8, 9, 10, 1, 2, 3};

Divide the array in half, start+end/2 = (0+8)/2 = 4.

Step 1: If the key to search is mid element then we found the match and return;

Step 2: At index 4, we have 9, so left sub-array is {5, 6, 7, 8} and right sub-array is {10, 1, 2, 3}
If you observe, either half would definitely be sorted in case of sorted rotated array.

Step 3: If the element to search is between the sorted half then repeat the steps for sorted sub-array, if not, repeat the steps for the unsorted sub-array


Java program to find element In Sorted Rotated Array.
package com.javabypatel.array;

/*
    Input:  array = {5, 6, 7, 8, 9, 10, 1, 2, 3}
            Key = 2
    Output: Index: 7

    Input:  array = {5, 1, 2, 3, 4}
            Key = 1
    Output: Index: 1

    Input:  array = {5, 1, 2, 3, 4}
            Key = 4
    Output: Index: 4

 */
public class SearchInRotatedSortedArray {

    public static void main(String args[]) {
        int arr[] = {5, 1, 2, 3, 4};
        int key = 4;
        System.out.println("Index of the element is : " + searchInSortedRotatedArray(arr, key, 0, arr.length - 1));
    }

    private static int searchInSortedRotatedArray(int[] arr, int key, int start, int end) {
        if (start > end) {
            return -1;
        }

        int mid = start + (end - start) / 2;

        if (arr[mid] == key) {
            return mid;
        }

        if (arr[mid] <= arr[end]) {
            if (key >= arr[mid] && key <= arr[end]) {
                return searchInSortedRotatedArray(arr, key, mid+1, end);
            } else {
                return searchInSortedRotatedArray(arr, key, start, mid-1);
            }
        }
        if (arr[start] <= arr[mid]) {
            if (key >= arr[start] && key <= arr[mid]) {
                return searchInSortedRotatedArray(arr, key, start, mid-1);
            } else {
                return searchInSortedRotatedArray(arr, key, mid+1, end);
            }
        }

        return -1;
    }
}
Categories: , ,

Post a Comment