Building a Rotated Sorted Array Search in Java: Understanding Pivot and Binary Search

What is a Rotated Sorted Array?

Consider a sorted array, for example:

[1, 2, 3, 4, 5, 6]

Now, if this array is rotated at some pivot, say at index 3, it would become:

[4, 5, 6, 1, 2, 3]

Notice that the array is still sorted, but it is divided into two parts. Our goal is to search for a target value in such arrays efficiently.

---

The Search Strategy

To search in a rotated sorted array, we need to:

1. Find the Pivot: The pivot is the point where the array transitions from larger to smaller values.
2. Binary Search: Once we find the pivot, we can use binary search on the appropriate half of the array.

---

Step-by-Step Code Explanation

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: " + result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot + 1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                return mid; // Target found
            } else if (target < arr[mid]) {
                end = mid - 1; // Search left half
            } else {
                start = mid + 1; // Search right half
            }
        }
        return -1; // Target not found
    }

    // Function to find the pivot index in a rotated sorted array
    static int searchPivot(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

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

            // Check if mid is the pivot point
            if (mid < end && arr[mid] > arr[mid + 1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] < arr[mid - 1]) {
                return mid - 1;
            }

            // Decide whether to move left or right
            if (arr[mid] <= arr[start]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1; // No pivot found (array is not rotated)
    }
}

---

Explanation of the Code

1. search():

   • This function is responsible for searching for the target in the rotated sorted array.
   • First, we find the pivot using the searchPivot() function.
   • Depending on the pivot's position, we then decide which half of the array to search using binary search.

2. binarySearch():

   • A standard binary search algorithm to find the target in a sorted sub-array.
   • We define the start and end indices and progressively narrow the search space.

3. searchPivot():

   • This function identifies the pivot point (the place where the array rotates).
   • The pivot is the index where the sorted order is "broken" (i.e., the array goes from a higher value to a lower value).
   • If no pivot is found, it means the array was not rotated, and we can perform a regular binary search.

---

How the Algorithm Works

For an array like [4, 5, 6, 1, 2, 3]:

• The pivot is at index 2 (6 is the largest, and it is followed by 1, the smallest).
• We use this pivot to divide the array into two parts: [4, 5, 6] and [1, 2, 3].
• If the target is greater than or equal to the first element (4 in this case), we search the left half. Otherwise, we search the right half.

This method ensures that we search efficiently, achieving a time complexity of O(log n), similar to a standard binary search.

---

Conclusion

Rotated sorted arrays are a common interview question and a useful challenge to deepen your understanding of binary search. By finding the pivot and adapting our binary search accordingly, we can efficiently search through the array in logarithmic time.

If you found this article helpful, feel free to connect with me on LinkedIn or share your thoughts in the comments! Happy coding!

The above is the detailed content of Building a Rotated Sorted Array Search in Java: Understanding Pivot and Binary Search. For more information, please follow other related articles on the PHP Chinese website!