Search element in a sorted and rotated array / find pivot where it is rotated

Problem Overview

The problem "Search in Rotated Sorted Array" is a classic algorithmic challenge that evaluates your understanding of binary search in a non-standard scenario. In this problem, you are given a sorted array that has been rotated at an unknown pivot, and your task is to find a target value within this array. If the target exists, return its index. Otherwise, return -1.

An array is rotated if, after some number of right shifts, the numbers shift to the position where the first part of the array is placed after the second part. For example, given the sorted array [4,5,6,7,0,1,2], it could be considered as rotated about the pivot index 4.

Understanding the Problem

You are tasked with searching a particular target in an array that appears to be jumbled due to rotation. There are several insights essential for tackling this problem:

• The array has two sorted sub-arrays.
• A rotated array maintains its internal ordering despite the shift.
• It’s crucial to figure out which part of the array is sorted to adjust the binary search algorithm accordingly.

The problem requires an understanding of how to adapt a binary search technique to work within the constraints of such an array.

Key DSA Concepts and Theory

Binary Search

Binary search is a fundamental searching technique with a time complexity of O(log n). It is typically used in scenarios involving sorted arrays. The basic idea is to repeatedly divide the search interval in half. If the value of the search key is less than the item in the middle, the search continues in the lower half, or lower interval, otherwise it continues in the upper half, eliminating half of the elements from the search space at every step.

Rotated Arrays

A rotated sorted array can be visualized as two individually sorted arrays. If you look at the example [4,5,6,7,0,1,2], this can be decomposed as [4,5,6,7] and [0,1,2]. This rotates around the pivot point, maintaining sorted segments across the array.

Solution Approach

The problem can be efficiently solved using a modified version of the binary search. Let's break down the step-by-step solution, showcasing the pathway to achieving log(n) complexity.

1. Initialization: Start by defining the initial boundary pointers: left (l) at the beginning of the array and right (r) at the end.

2. Binary Search Mechanism: While l is less than or equal to r, calculate the midpoint (mid) index; since rotations maintain non-decreasing order across boundaries, we utilize these properties in comparison:

   • Current Sorted Half: Determine which half [l:mid] or [mid:r] is sorted.

   • Target Location Check: Once determined, decide if the target can be in this half using comparisons; adjust search space accordingly.

3. Adjust Search Space: If the target is not within the current half, adjust the pointers l or r to explore the other half.

Here's the code to implement the solution in C++ and Java:

C++ Implementation

#include <vector>

int search(std::vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size() - 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;

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

        // Determine which half is sorted
        if (nums[l] <= nums[mid]) { // Left half is sorted
            if (nums[l] <= target && target < nums[mid]) {
                r = mid - 1; // Target is in sorted half
            } else {
                l = mid + 1;
            }
        } else { // Right half is sorted
            if (nums[mid] < target && target <= nums[r]) {
                l = mid + 1; // Target is in sorted half
            } else {
                r = mid - 1;
            }
        }
    }

    return -1;
}

Java Implementation

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

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

            // Check which side is sorted
            if (nums[l] <= nums[mid]) { // Left side is sorted
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1; // Target in sorted side
                } else {
                    l = mid + 1;
                }
            } else { // Right side is sorted
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1; // Target in sorted side
                } else {
                    r = mid - 1;
                }
            }
        }

        return -1;
    }
}

Time and Space Complexity Analysis

The algorithm benefits from the efficiency of binary search, thus having:

• Time Complexity: O(log n), which is achieved through halving the search space with each iteration.
• Space Complexity: O(1), since no additional data structures are used dependent on input size.

Common Mistakes to Avoid

• Misidentifying the sorted half.
• Incorrectly updating the boundaries (l and r).
• Forgetting to check equality with the target at mid before deciding the direction of search.

Similar Problems on LeetCode

Here are some similar problems you can practice:

• LeetCode 81: Search in Rotated Sorted Array II
• LeetCode 153: Find Minimum in Rotated Sorted Array
• LeetCode 154: Find Minimum in Rotated Sorted Array II

Additional Resources and References

• Binary Search Tutorial - Geeks for Geeks
• LeetCode Discuss - Community Solutions
• YouTube: Rotated Sorted Array Solutions

This article references various educational resources to deepen your understanding of binary search applications in non-standard arrays. Keeping practice with diverse problems ensures that your adaption of these techniques becomes second nature in programming challenges.