Search in Rotated Sorted Array - Java Solution

1. Introduction

This post delves into a common problem in algorithm design: searching for a target value in a rotated sorted array. This problem illustrates the application of binary search in a modified array where the sorting order is altered by rotation at an unknown pivot.

Problem

Given an integer array nums sorted in ascending order and then rotated at some unknown pivot, along with an integer target, the task is to return the index of target in nums, or -1 if it is not found. The solution must achieve O(log n) runtime complexity.

2. Solution Steps

1. Perform a binary search on the array.

2. Identify if the target lies in the rotated part or the normally sorted part.

3. Adjust the search range based on the position of the target.

4. Continue the binary search until the target is found or the search space is exhausted.

5. Return the index of the target, or -1 if not found.

3. Code Program

public class SearchRotatedSortedArray {
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        System.out.println(search(nums, target)); // Test the function
    }

    // Function 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 the left side is sorted
            if (nums[start] <= nums[mid]) {
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else { // Right side is sorted
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}

Output:

4

Explanation:

1. search: The function implements a modified binary search on a rotated sorted array.

2. It determines the midpoint of the current search range.

3. The function then checks if the target lies within the sorted portion of the array.

4. Depending on whether the target is in the rotated or sorted part, it adjusts the search range accordingly.

5. The process continues, halving the search space each time, until the target is found or the range is exhausted.

6. The function returns the index of the target or -1 if it is not found, ensuring O(log n) runtime complexity.