Tuesday, 2 April 2019

Search element In Sorted Rotated Array in Java

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;
    }
}
at

No comments:

Post a Comment