Search in Rotated Sorted Array - Java Solution

1. Introduction

This blog post focuses on solving a unique problem in array manipulation: searching for a target value in a rotated sorted array. In this scenario, a sorted array is rotated at some unknown pivot, and the challenge is to efficiently find a target value in this modified array using an approach with O(log n) runtime complexity.

Problem

Given a rotated sorted array and a target value, find the index of the target if it's present in the array, otherwise return -1.

Example 1:

Input: nums = [8, 11, 13, 15, 1, 4, 6], target = 1

Output: 4

Example 2:

Input: nums = [1, 4, 6, 8, 11, 13, 15], target = 3

Output: -1

2. Solution Steps

1. Apply binary search to find the pivot point where the array is rotated.

2. Once the pivot is found, perform a binary search in the appropriate half of the array where the target is likely to be found.

3. If the target is found, return its index; otherwise, return -1.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] nums1 = {8, 11, 13, 15, 1, 4, 6};
        System.out.println("Index of 1: " + search(nums1, 1));

        int[] nums2 = {1, 4, 6, 8, 11, 13, 15};
        System.out.println("Index of 3: " + search(nums2, 3));
    }

    // Method to search in a rotated sorted array
    public static int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1;

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

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

            // Check if left half is sorted
            if (nums[start] <= nums[mid]) {
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
            // Right half is sorted
            else {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1; // Target not found
    }
}

Output:

Index of 1: 4
Index of 3: -1

Explanation:

The search method applies a modified binary search to efficiently find the target in a rotated sorted array. It first identifies which half of the array is sorted and then decides the search range accordingly. 

For instance, in the array [8, 11, 13, 15, 1, 4, 6] with target 1, the method correctly identifies the sorted part of the array and finds 1 at index 4. 

For the second example, the target 3 is not found in the array, resulting in -1.