Java Program for Search an element in Rotated Sorted Array

Search target element in Rotated and Sorted Array in Java with explanation

Problem Description :

Given a sorted and rotated array nums[] of size N and a target, the task is to find the target in the nums[] array.

Array is sorted but it is also rotated. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Example 1 :

Input:  nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Example 2 :

Input: nums = [4,5,6,7,0,1,2], target = 8

Output: -1

Example 3 :

Input: nums = [1,2,3,4,6,8,12,15], target = 2

Output : 1

Example 4 :

Input: nums = [2, 4, 8, 16, 32, 0, 1], target = 5

Output: -1

Here we can use binary search, but given array is rotated so we have to apply extra logic with binary search.

Solution 1 : Searching target element from rotated sorted array in Java

import java.util.Scanner;

public class SearchInRotatedSortedArray {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.println("Enter array size : ");

        int size = sc.nextInt();

        int[] array = new int[size];

        // Taking user inputs

        System.out.println("Enter array elements :");

        for (int i = 0; i < array.length; i++) {

            array[i] = sc.nextInt();

        }

        System.out.println("Enter target : ");

        int target = sc.nextInt();

        System.out.println("Output : "+search(array, target));

    }

    

    public static int search(int[] nums, int target) {

        

        int start = 0;

        int end = nums.length-1;

        while (start <= end) {

            int mid = (start+end)/2;

        

            if (nums[mid] == target) return mid;

            

            if (nums[start] <= nums[mid]) {

              
                // checking target is in between start and mid
if (nums[mid] > target && target >= nums[start]) {
    end = mid-1;
                } else {
    start = mid+1;
        }
    } else {

                // checking target is in between mid and end
if (nums[mid] < target && target <= nums[end]) {
         start = mid+1;
} else {
    end = mid-1;
}
    }

        }

        return -1;

    }

}

Solution Explanation :

• Create two variables, start and end. Assign 0 to start and array length to end.
• While loop til start < end
• Get mid index.
• In outer if else condition, check for start element is less or greater than mid element.
• If the entire left part is increasing, which means the pivot point is on the right part
  • If start < target < mid -> drop the right half
  • Else -> drop the left half
• If the entire right part is increasing, which means the pivot point is on the left part
  • If mid < target < end -> drop the left half
  • Else -> drop the right half

 

Similar tutorials :

• Find First and Last Position of Element in Sorted Array 
• Find Triplets Sum equal to given Target in Java