Help Rahul To Search [codingblocks]

Rahul had a sorted array of numbers from which he had to find a given number quickly. His friend by mistake rotated the array. Now Rahul doesn't have time to sort the elements again. Help him to quickly find the given number from the rotated array.

Hint - Think Binary Search!

Input Format
The first line contains N - the size of the array. the next N lines contain the numbers of the array.The next line contains the item to be searched.

Constraints
Output Format
Output the index of number in the array to be searched. Output -1 if the number is not found.

Sample Input
5
4
5
1
2
3
2

Sample Output
3

Explanation
The given rotated array is [4, 5, 1, 2, 3]. The element to be searched is 2 whose index is 3.

Java Code:

IDE code: https://ide.geeksforgeeks.org/NDBKfjPiuJ

/*
Amit Kumar
06-12-2020
IDE Code: https://ide.geeksforgeeks.org/NDBKfjPiuJ
*/

package array;
import java.util.Scanner;

public class Array_HelpRahulToSearch {
    public static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) {
        int size = scanner.nextInt();
        int[] arr = new int[size];
        for (int i=0; i<size; i++) {
            arr[i] = scanner.nextInt();
        }
        int element = scanner.nextInt();
        System.out.println(modifiedBinarySearch(arr, element));
    }

    private static int modifiedBinarySearch(int[] arr, int element) {

        int breakPoint = arr.length-1;
        for (int i=0; i<arr.length-1; i++) {
            if (arr[i] > arr[i+1]) {
                breakPoint = i;
            }
        }

        int start = 0;
        int end = breakPoint;
        int mid;

        while (start <= end) {
            mid = (start+ end)/2;
            if (arr[mid] == element){
                return mid;
            } else if (arr[mid] > element) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        //this check means whole list is sorted
        if (breakPoint == arr.length-1) {
            return -1;
        }

        start = breakPoint + 1;
        end = arr.length - 1;

        while (start <= end) {
            mid = (start+ end)/2;
            if (arr[mid] == element){
                return mid;
            } else if (arr[mid] > element) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1;
    }
}