Search in a Rotated Sorted Array: Explanation and Efficient Solutions

Last update on May 18 2024 12:59:37 (UTC/GMT +8 hours)

Problem Statement

Search in a Rotated Sorted Array:

Search for a target value in a rotated sorted array.

Introduction to the Problem
Underlying Concepts
Examples and Illustrations
Brute Force Approach
Optimization Techniques
Algorithmic Thinking
Algorithm Strategies
Common Mistakes and Pitfalls
Coding Best Practices
Testing and Debugging
Algorithm Analysis
Application in Real-world Projects
Solution for different languages
Time and Space Complexity

Introduction to the Problem

Problem Statement: Searching for a target value in a rotated sorted array involves finding the index of a specific value within an array that has been rotated at an unknown pivot point. The array was originally sorted in ascending order, but it was rotated such that some elements may have shifted to the beginning or end of the array. The goal is to efficiently determine whether the target value exists in the array and, if so, return its index; otherwise, return -1.

Input and output requirements:

Input:

The problem requires a rotated sorted array as input.
Additionally, it needs a target value to search for within the array.
The array can comprise of integers or other comparable data types.

Output:

The output is the index of the target value within the array if found.
If the target value is not found within the array, the output is -1.

Real-world Scenario: Consider a scenario where a library has a shelf of books sorted alphabetically by author's last name. Due to renovations, the shelf gets accidentally rotated, causing some books to shift positions. Now, a librarian needs to find a specific book by its author's last name. They must efficiently search through the rotated shelf to locate the book without manually rearranging all the books back into their original order.

Underlying Concepts:

Rotated Sorted Array:
- A rotated sorted array is an array that was originally sorted in ascending order but has been rotated at some pivot point. For example, if the original sorted array was [1, 2, 3, 4, 5], rotating it by 2 positions to the right would result in [4, 5, 1, 2, 3]. Despite the rotation, elements within the array segments remain sorted.
- This rotation can occur in either direction, left or right, and the pivot point can vary.
Search Algorithms:

Search algorithms are methods used to find a particular element within a collection of data. For the problem of searching in a rotated sorted array, common search algorithms like binary search are particularly relevant.
Binary search is efficient for sorted arrays. While a rotated sorted array isn't strictly sorted, it still exhibits sorted properties within certain segments. Binary search can exploit this property by searching in the sorted segments to find the target element efficiently.

Examples and Illustrations:

Walkthrough examples:

Example 1:

Suppose the rotated sorted array is [4, 5, 6, 7, 0, 1, 2] and the target value is 6.
Steps:

Identify the Pivot: Notice that the array is rotated around the element 7.
Binary Search Adaptation: Since the array is divided into two sorted halves [4, 5, 6, 7] and [0, 1, 2], we adapt binary search to identify the segment in which the target resides.
Midpoint Comparison: The midpoint of the entire array is 7. Since 6 < 7, search the left half [4, 5, 6, 7].
Repeat Steps: Continue binary search within the left segment until the target 6 is found at index 2.

Example 2:

Consider the array [6, 7, 1, 2, 3, 4, 5] with target value 3.
Steps:

Identify the Pivot: The array is rotated around 7.
Binary Search Adaptation: Identify segments [6, 7] and [1, 2, 3, 4, 5].
Midpoint Comparison: The midpoint of the entire array is 2. Since 3 > 2, search the right half [1, 2, 3, 4, 5].

Repeat Steps: Continue binary search within the right segment until the target 3 is found at index 4.

Brute Force Approach:

Naive Solution:

The brute force approach is the most straightforward method to solve the problem. It involves checking each element in the array one by one to find the target value.
Steps:

Step 1: Iterate through the entire array from the first element to the last.
Step 2: For each element, compare it with the target value.
Step 3: If an element matches the target value, return its index.
Step 4: If the loop completes without finding the target, return -1.

Example:

Given the rotated sorted array [4, 5, 6, 7, 0, 1, 2] and target 6:

Step 1: Start at the first element 4, compare it with 6. No match.
Step 2: Move to the next element 5, compare it with 6. No match.
Step 3: Move to the next element 6, compare it with 6. Match found.
Step 4: Return the index 2.

Code Example:

def brute_force_search(intervals, target):
    for i in range(len(intervals)):
        if intervals[i] == target:
            return i
    return -1

# Test case
print(brute_force_search([4, 5, 6, 7, 0, 1, 2], 6))  # Output: 2

Complexity Analysis:

Time Complexity:

The time complexity of the brute force approach is (𝑛), where 𝑛n is the number of elements in the array. This is because in the worst case, we might have to check every element in the array.
Best Case: The target is the first element, so the time complexity is (1).
Worst Case: The target is the last element or not present, so the time complexity is (𝑛).

Space Complexity:

The space complexity of the brute force approach is (1) because no extra space is required other than a few variables for iteration and comparison.

Limitations:

Inefficiency: The brute force approach is inefficient for large arrays because it requires examining each element, leading to higher execution time.
Not Leveraging Array Properties: This approach does not take advantage of the fact that the array is sorted and rotated, which could be used to find a more efficient solution.

Optimization Techniques

Binary Search: Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half.

Steps for "Rotated Sorted Array":

Step 1: Initialize two pointers, left at the start (index 0) and right at the end (last index) of the array.
Step 2: Find the middle index, mid, by calculating (left + right) / 2.
Step 3: Compare the middle element with the target value:

If the middle element is the target, return the middle index.
If not, determine which part of the array (left or right) is normally ordered.

Step 4: If the left part is normally ordered (i.e., array[left] <= array[mid]):

Check if the target is within this range (array[left] <= target < array[mid]). If yes, adjust the right pointer to mid - 1.
If not, adjust the left pointer to mid + 1.

Step 5: If the right part is normally ordered (i.e., array[mid] <= array[right]):

Check if the target is within this range (array[mid] < target <= array[right]). If yes, adjust the left pointer to mid + 1.
If not, adjust the right pointer to mid - 1.

Step 6: Repeat the steps until the pointers cross, meaning the target is not in the array.

Handling Rotation:

In a rotated sorted array, part of the array is ordered, and part of it is not. By determining which part is ordered, you can eliminate half of the array from the search space at each step.

Steps:
- Determine if the left or right portion of the array is sorted by comparing the middle element with the boundary elements.
- Adjust the search space based on whether the target is within the sorted portion.
- Continue adjusting the search space until the target is found or the search space is exhausted.
Example:

Given the rotated sorted array [4, 5, 6, 7, 0, 1, 2] and target 6:

Step 1: Initial pointers: left = 0, right = 6, mid = 3.
Step 2: The left part [4, 5, 6, 7] is sorted.
Step 3: Since 4 <= 6 < 7, adjust right to mid - 1 = 2.
Step 4: New pointers: left = 0, right = 2, mid = 1.
Step 5: The target is 6, which is found at index 2.

Let's go through the example where the rotated sorted array is [4, 5, 6, 7, 0, 1, 2] and the target value is 0.

Example:

Initial Pointers:

left = 0 (value 4)
right = 6 (value 2)
mid = (left + right) / 2 = (0 + 6) / 2 = 3 (value 7)

Identify the Sorted Part:

Compare array[left] (4) and array[mid] (7).
Since array[left] <= array[mid] (4 <= 7), the left part [4, 5, 6, 7] is sorted.

Check Target in the Sorted Part:

Check if the target 0 is within the sorted range [4, 5, 6, 7].
Since 0 is not in the range 4 to 7, adjust the left pointer to mid + 1 = 4.

New Pointers:

left = 4
right = 6
mid = (left + right) / 2 = (4 + 6) / 2 = 5 (value 1)

Identify the Sorted Part Again:

Compare array[left] (0) and array[mid] (1).
Since array[left] <= array[mid] (0 <= 1), the left part [0, 1] is sorted.

Check Target in the Sorted Part:

Check if the target 0 is within the sorted range [0, 1].
Since 0 is in the range 0 to 1, adjust the right pointer to mid - 1 = 4.

Final Pointers:

left = 4
right = 4
mid = (left + right) / 2 = (4 + 4) / 2 = 4 (value 0)

Target Found:

The target 0 is found at index 4.

Steps Recap:

Initially, determine that the left part [4, 5, 6, 7] is sorted.
Since 0 is not within [4, 5, 6, 7], adjust the search to the right part.
Determine that the new left part [0, 1] is sorted.
Since 0 is within [0, 1], narrow the search to this part.
Finally, find target 0 at index 4.

Complexity Analysis:

Time complexity:

The time complexity of binary search in a rotated sorted array is 𝑂(log⁡𝑛), where n is the number of elements in the array. This is because each step reduces the search space by half.

Space complexity:

The space complexity of the binary search approach is 𝑂(1), as it only requires a constant amount of extra space for pointers and variables.

Comparison with Brute Force:

Brute Force:

Time Complexity: 𝑂(n) - Each element is checked individually.
Space Complexity: 𝑂(1) - No additional space is used.

Binary search:

Time Complexity: 𝑂(log𝑛) - The search space is halved with each step.
Space Complexity: 𝑂(1) - No additional space is used.

Advantages of Binary Search:

Significantly faster than brute force, especially for large arrays.
Efficiently leverages the properties of sorted arrays to minimize the number of comparisons.

Algorithmic Thinking:

Divide and Conquer:

Concept Overview:

Divide and conquer is a powerful algorithmic strategy that involves breaking a problem down into smaller subproblems, solving each subproblem independently, and then combining their solutions to solve the original problem.
This approach is particularly effective for problems that can be recursively divided into simpler instances of the same problem.

Application to Rotated Sorted Array:

In the context of searching for a target value in a rotated sorted array, divide and conquer can be implemented through a modified binary search.
The idea is to divide the array into two halves, identify which half contains the sorted segment, and determine if the target value lies within this sorted segment.
By repeatedly halving the search space and focusing only on the relevant portion of the array, we can quickly narrow down the location of the target value.

Steps in Binary Search for a Rotated Sorted Array:

Initial setup:

Set two pointers, left and right, to the start and end of the array, respectively.

Finding the midpoint:

Calculate the midpoint index mid = (left + right) / 2.

Determine the Sorted Half:

Compare the values at the left and mid indices to determine which half of the array is sorted.

Adjust Search Range:

If the target is within the sorted half, adjust the right pointer to narrow the search to this half.
If the target is not within the sorted half, adjust the left pointer to exclude this half and focus on the other half.

Repeat Until Found or Exhausted:

Repeat the process until the target value is found or the search range is exhausted.

Algorithmic Strategies:

Using Divide and Conquer Efficiently:

Divide and conquer strategies, such as the modified binary search, leverage the inherent structure of the problem (e.g., the sorted segments in a rotated array) to reduce the search space and improve efficiency.
This approach is contrasted with brute force methods, which might involve examining each element individually and are typically less efficient.

Advantages of Divide and Conquer:

Efficiency:

Reduces the number of comparisons needed to find the target value, leading to faster search times.

Scalability:

Handles larger datasets more effectively compared to brute force approaches, which can become impractical as the array size grows.

Simplicity:

Once understood, divide and conquer algorithms are often simpler to implement and reason about due to their recursive nature.

Common Mistakes and Pitfalls:

Edge Cases:

Edge cases are scenarios that occur at the extreme ends of the input spectrum, and they often reveal hidden bugs or flaws in an algorithm.
Potential Edge Cases:

Empty Array:

Description:

An empty array has no elements to search.

Handling:

Before proceeding with the search, check if the array is empty and return -1 if it is.

Example:

Input: [], target = 3
Output: -1

Single Element Array:
An array with only one element where the element could be the target or not.

Handling:

Directly compare the single element with the target and return the appropriate index or -1.

Example:

Input: [1], target = 1
Output: 0
Input: [1], target = 2
Output: -1

Duplicates:
Arrays containing duplicate elements can complicate the search process.

Handling:

Ensure the algorithm accounts for the presence of duplicates without causing incorrect results or infinite loops.

Example:

Input: [2, 2, 2, 3, 4], target = 3
Output: 3

Target Not Present:

Description:

The target value is not present in the array.

Handling:

The algorithm should correctly return -1 when the target is not found.

Example:

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

Handling Rotated Arrays:

Identifying the Pivot Point:
In a rotated sorted array, the pivot point is where the rotation occurs, dividing the array into two sorted subarrays.

Importance:

Identifying the pivot point helps in determining which part of the array to search, making the algorithm efficient.

Challenges in Identifying the Pivot Point:

Unsorted Segments:

The rotation creates unsorted segments, making it tricky to apply standard binary search directly.

Mixed Sorted Order:

The array is not strictly increasing due to the rotation, requiring careful examination to identify the pivot.

Strategies for Identifying the Pivot Point:

Binary search adaptation:

Steps:

Use a modified binary search to identify the pivot point by comparing the middle element with the left and right boundaries.

Process:

Compare the middle element with the leftmost element. If the middle element is greater, the left half is sorted. Otherwise, the pivot is in the left half.

Using Indices:

Steps:

Compare elements at calculated indices to identify the point where the order breaks.

Example:

Input: [4, 5, 6, 7, 0, 1, 2]
Pivot Point: 4 (index of element 0)

Example Walkthrough:

Scenario:

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

Steps:

Initial array: [4, 5, 6, 7, 0, 1, 2]
Determine the middle element: 7 (index 3)
Identify the sorted half: [4, 5, 6, 7] (left half)
Adjust search range: [0, 1, 2] (right half)
Apply binary search on the adjusted range.

Coding Best Practices:

Modularity:

Modularity refers to dividing a program into separate, independent, and reusable components or functions. Each function should handle a specific task, making the code easier to understand, maintain, and debug.

Importance in Searching in Rotated Sorted Arrays:

When dealing with complex problems like searching in a rotated sorted array, modularity helps in breaking down the solution into manageable pieces.
It allows for better organization and separation of concerns, ensuring that each function has a single responsibility.

Implementation Tips:

Function Decomposition:

Break down the solution into multiple functions, such as:

findPivot(arr) to find the pivot point in the rotated array.
binarySearch(arr, target, start, end) to perform binary search on a specified range.
searchInRotatedArray(arr, target) as the main function to coordinate the search process.

Example:

def findPivot(arr):
    # Function to find the pivot point
    pass

def binarySearch(arr, target, start, end):
    # Function to perform binary search on a range
    pass

def searchInRotatedArray(arr, target):
    # Main function to search for the target in a rotated sorted array
    pass

Benefits:

Readability:

Modular code is easier to read and understand because each function has a clear purpose.

Maintainability:

Changes or updates can be made to individual functions without affecting the entire codebase.

Reusability:

Functions can be reused in different parts of the program or in other projects.

Variable Naming:

Concept Overview:

Meaningful variable names enhance code readability by clearly indicating the purpose and usage of each variable. Poorly named variables can lead to confusion and errors.

Importance in Searching in Rotated Sorted Arrays:

Clear variable names help in understanding the logic and flow of the algorithm, especially in a complex problem involving multiple steps and calculations.
They make the code self-documenting, reducing the need for excessive comments.

Best Practices:

Descriptive Names:

Use names that describe the variable's role, such as ‘start’, ‘end’, ‘mid’, ‘pivot’, ‘target’, and ‘index’.
Avoid single-letter names like i, j, or k unless used in very small scopes like simple loops.

Consistency:

Follow a consistent naming convention, such as “camelCase” or “snake_case”, throughout the code.

Avoid Abbreviations:

Use full words to avoid ambiguity. For example, use index instead of ‘idx’.

Example:

def searchInRotatedArray(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        # Check if the mid element is the target
        if arr[mid] == target:
            return mid

        # Determine which half is sorted
        if arr[left] <= arr[mid]:  # Left half is sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half is sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Benefits:

Clarity:

Well-named variables make the code's purpose clear at a glance.

Debugging:

Meaningful names make it easier to trace and debug the code.

Collaboration:

Code with clear variable names is easier to understand and maintain by other developers working on the project.

Testing and Debugging:

Test Cases:

Test cases are specific inputs and outputs used to verify that the code works correctly under various conditions. They help ensure the solution handles all possible scenarios, including edge cases and common cases.

Importance in Searching in Rotated Sorted Arrays:

Proper test cases validate that the algorithm correctly identifies the target value in both rotated and non-rotated arrays. They ensure the code handles all possible configurations of the input array.

Key Scenarios to Cover:

Basic Cases:

Simple cases where the array is rotated, and the target is present.

Example: Array: [4, 5, 6, 7, 0, 1, 2], Target: 0, Expected Output: 4

Non-Rotated Array:

Cases where the array is not rotated to ensure the algorithm still works correctly.

Example: Array: [1, 2, 3, 4, 5, 6, 7], Target: 4, Expected Output: 3

Target Not Present:

Cases where the target value is not present in the array.

Example: Array: [4, 5, 6, 7, 0, 1, 2], Target: 3, Expected Output: -1

Single Element Array:

Cases where the array contains only one element.

Example: Array: [1], Target: 1,
Expected Output: 0
Example: Array: [1], Target: 2,
Expected Output: -1

Empty Array:

Edge case where the array is empty.

Example: Array: [], Target: 1, Expected Output: -1

Duplicates:

Cases where the array contains duplicate values.

Example: Array: [2, 2, 2, 3, 4, 2], Target: 3, Expected Output: 3

Debugging techniques:

Debugging involves identifying and fixing errors or bugs in the code. It is an essential part of the development process, ensuring the solution works as expected.

Importance in Searching in Rotated Sorted Arrays:

Debugging helps to find and fix logical errors, off-by-one errors, and other issues that may arise when implementing the search algorithm in a rotated sorted array.

Common Debugging Techniques:

Print Statements:

Use print statements to output the values of variables at different stages of the algorithm.
Helps track the flow of execution and identify where things go wrong.

Step-by-Step Execution:

Use a debugger to step through the code line by line.
Allows you to examine the state of the program at each step and verify that it behaves as expected.

Boundary Checks:

Ensure that the algorithm correctly handles boundary conditions, such as the start and end indices of the array.
Helps prevent off-by-one errors.

Algorithm Analysis:

Time and Space Complexity:

Concept Overview:

Time complexity refers to the amount of time an algorithm takes to complete as a function of the input size.
Space complexity refers to the amount of memory an algorithm uses as a function of input size.

Binary Search in a Rotated Sorted Array:

The binary search algorithm splits the search space in half at each step, significantly reducing the number of comparisons needed.
Time Complexity:

The time complexity of binary search in a rotated sorted array is O(logn), where 𝑛n is the number of elements in the array. This is because each iteration of the algorithm reduces the search space by half.

Space Complexity:

The space complexity of the binary search algorithm is O(1). This is because it uses a constant amount of additional memory, irrespective of the input size, for variables like 'left', 'right', and 'mid'.

Example Analysis:

Given:

Array: [4, 5, 6, 7, 0, 1, 2]
Target: 0

Steps:

Initialize 'left' to 0 and 'right' to 6 (array length - 1).
Calculate 'mid' as (0+6)/2 = 3.
Compare arr[mid] (7) with target (0).
Determine the sorted part (left half in this case).
Adjust 'left' and 'right' pointers.
Repeat until 'left' exceeds 'right' or target is found.

Iterations:

With each iteration, the search space is halved, leading to a logarithmic number of comparisons.

Trade-offs:

Concept Overview:

Trade-offs involve balancing different aspects of the algorithm's performance, such as time complexity and space complexity, to achieve an optimal solution.

Time vs. Space Complexity:

Binary Search:

The primary trade-off in binary search is between time and space complexity.
Binary search is highly time-efficient (O(logn)) but requires careful handling of array indices and comparisons.
Space efficiency is optimal (O(1)), making it suitable for large datasets.

Brute Force Approach:

In contrast, the brute force approach has a time complexity of O(n)O(n), where 𝑛n is the number of elements. It iterates through the entire array, making it slower for large datasets.
However, its space complexity is also O(1) as it doesn't require additional memory.

Impact of Optimization Techniques:

Binary Search:

Significantly reduces the number of comparisons needed.
Effective for large arrays due to its logarithmic time complexity.
Requires careful implementation to handle rotated parts and avoid errors.

Brute Force:

Easier to implement and understand.
Inefficient for large datasets due to linear time complexity.
Better for small arrays or when simplicity of implementation is a priority.

Example scenario:

Binary search efficiency:

For an array of size 1,000,000, binary search will require at most 20 comparisons (log21,000,000≈20).
Brute force would require up to 1,000,000 comparisons in the worst case.

Resource constraints:

If memory is a constraint, binary search is preferable due to its minimal additional memory requirement.
If execution speed is a constraint, binary search is again preferable due to its logarithmic time complexity.

Application in Real-world Projects:

Example Use Cases:

Searching in Rotated Logs:

Scenario:

Consider a system that rotates its log files for archival purposes. Each log file is time-stamped, and the system needs to search for specific events across these rotated logs.

Application:

An algorithm to search within these rotated logs can efficiently locate specific log entries by treating the logs as a rotated sorted array and applying the binary search technique.

Database Indexing:

Scenario:

In databases, indexes can be partially or fully rotated due to various operations such as maintenance or balancing. Searching for specific records within these rotated indexes is a common requirement.

Application:

Using an optimized search algorithm for rotated sorted arrays can enhance the performance of database queries by quickly locating the required records.

Circular Buffers:

Scenario:

Circular buffers, used in network programming and real-time systems, often wrap around when they reach their capacity. Searching for specific data within a circular buffer is analogous to searching in a rotated sorted array.

Application:

Applying search techniques for rotated arrays can help efficiently manage and query circular buffers.

Rotated Data Structures:

Scenario:

In some applications, data structures may be rotated as part of the operations, such as in certain encryption algorithms or data storage strategies.

Application:

Algorithms for searching in rotated sorted arrays can be adapted to handle these scenarios, ensuring quick and efficient data retrieval.

Solution for different languages:

Python - Search in a Rotated Sorted Array

Code:

def search(nums, target):
    # Initialize pointers for binary search
    left, right = 0, len(nums) - 1

    while left <= right:
        # Find the middle index
        mid = (left + right) // 2

        # Check if the target is at the mid position
        if nums[mid] == target:
            return mid
        
        # Determine which side is sorted
        if nums[left] <= nums[mid]:
            # Left side is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right side is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    # If the target is not found
    return -1

# Test cases
print(search([4, 5, 6, 7, 0, 1, 2], 6))  # Output: 2
print(search([4, 5, 6, 7, 0, 1, 2], 0))  # Output: 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))  # Output: -1
print(search([1], 0))  # Output: -1
print(search([1, 3], 3))  # Output: 1

Output:

Explanation of the said Python code:

Initialization:

Two pointers, 'left' and 'right', are set to the start and end of the array, respectively.

Binary search loop:

The loop continues while 'left' is less than or equal to 'right'.

Middle Index calculation:

The middle index, 'mid', is computed.

Target Check:

If the target value is at the middle index, return 'mid'.

Determine the Sorted Side:

Check if the left side of the array (from 'left' to 'mid') is sorted.

Search in Sorted Side:

If the left side is sorted and the target is within this range, adjust the 'right' pointer to 'mid - 1'.
Otherwise, adjust the 'left' pointer to 'mid + 1'.

Search in the Unsorted Side:

If the left side is not sorted, then the right side must be sorted. If the target is within this range, adjust the 'left' pointer to 'mid + 1'.
Otherwise, adjust the 'right' pointer to 'mid - 1'.

Return Not Found:

If the loop ends without finding the target, return -1.

Java - Search in a Rotated Sorted Array

Code:

public class SearchRotatedSortedArray {
    public int search(int[] nums, int target) {
        // Initialize pointers for binary search
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            // Find the middle index
            int mid = (left + right) / 2;

            // Check if the target is at the mid position
            if (nums[mid] == target) {
                return mid;
            }

            // Determine which side is sorted
            if (nums[left] <= nums[mid]) {
                // Left side is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // Right side is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        // If the target is not found
        return -1;
    }

    public static void main(String[] args) {
        SearchRotatedSortedArray search = new SearchRotatedSortedArray();
        
        // Test cases
        System.out.println(search.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 6));  // Output: 2
        System.out.println(search.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));  // Output: 4
        System.out.println(search.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));  // Output: -1
        System.out.println(search.search(new int[]{1}, 0));  // Output: -1
        System.out.println(search.search(new int[]{1, 3}, 3));  // Output: 1
    }
}

Output:

Explanation of the said Java code:

Binary Search Function:

The "search()" function implements binary search to find the target value in the rotated sorted array.

Initialization:

Initialize two pointers, 'left' and 'right', to the start and end of the array, respectively.

Binary Search Loop:

While 'left' is less than or equal to 'right', the loop continues.

Middle Index Calculation:

The middle index, 'mid', is calculated as (left + right) / 2.

Target Check:

If the target value is found at the middle index, return the index 'mid'.

Determine Sorted Side:

Determine which side of the array is sorted by comparing 'nums[left]' with 'nums[mid]'.

Search in Sorted Side:

If the left side is sorted and the target is within the range of the sorted left side, adjust the 'right' pointer to 'mid - 1'.
Otherwise, adjust the 'left' pointer to 'mid + 1'.

Search in Unsorted Side:

If the left side is not sorted, then the right side must be sorted. If the target is within the range of the sorted right side, adjust the 'left' pointer to 'mid + 1'.
Otherwise, adjust the 'right' pointer to 'mid - 1'.

Return Not Found:

If the target is not found after the loop ends, return -1.

Main Function:

In the "main()" function, test cases are provided to validate the "search()" function.

C++ - Search in a Rotated Sorted Array

Code:

#include <iostream>
#include <vector>

using namespace std;

int search(vector<int>& nums, int target) {
    // Initialize pointers for binary search
    int left = 0, right = nums.size() - 1;

    while (left <= right) {
        // Find the middle index
        int mid = left + (right - left) / 2;

        // Check if the target is at the mid position
        if (nums[mid] == target) {
            return mid;
        }

        // Determine which side is sorted
        if (nums[left] <= nums[mid]) {
            // Left side is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right side is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    // If the target is not found
    return -1;
}

// Test cases
int main() {
    vector<int> nums1 = {4, 5, 6, 7, 0, 1, 2};
    vector<int> nums2 = {4, 5, 6, 7, 0, 1, 2};
    vector<int> nums3 = {4, 5, 6, 7, 0, 1, 2};
    vector<int> nums4 = {1};
    vector<int> nums5 = {1, 3};

    cout << search(nums1, 6) << endl;  // Output: 2
    cout << search(nums2, 0) << endl;  // Output: 4
    cout << search(nums3, 3) << endl;  // Output: -1
    cout << search(nums4, 0) << endl;  // Output: -1
    cout << search(nums5, 3) << endl;  // Output: 1

    return 0;
}

Output:

Explanation of the said C++ code:

Function definition (search):

The function "search()" takes a reference to a vector of integers ('nums') and an integer 'target'.

Initialization:

Two pointers 'left' and 'right' are initialized to the start (0) and end (nums.size() - 1) of the vector, respectively.

Binary search loop:

A while loop continues as long as 'left' is less than or equal to 'right'.

Middle Index calculation:

The middle index 'mid' is calculated as 'left + (right - left) / 2' to prevent overflow.

Target Check:

If the 'target' is found at the 'mid' position, return 'mid'.

Determine the Sorted Side:

Check if the left side of the array (nums[left] to nums[mid]) is sorted.
If it is, determine if the 'target' lies within this sorted portion. Adjust 'right' pointer if 'target' is within this range; otherwise, adjust 'left' pointer.

Search in Unsorted Side:

If the left side is not sorted, then the right side (nums[mid] to nums[right]) must be sorted. Check if 'target' lies within this sorted portion. Adjust 'left' pointer if 'target' is within this range; otherwise, adjust 'right' pointer.

Return Not Found:

If the 'target' is not found after the loop ends, return -1.

Main function:

The "main()" function tests the `search' function with several test cases.

C# - Search in a Rotated Sorted Array

Code:

using System;

public class SearchRotatedSortedArray
{
    public int Search(int[] nums, int target)
    {
        // Initialize pointers for binary search
        int left = 0, right = nums.Length - 1;

        while (left <= right)
        {
            // Find the middle index
            int mid = (left + right) / 2;

            // Check if the target is at the mid position
            if (nums[mid] == target)
            {
                return mid;
            }

            // Determine which side is sorted
            if (nums[left] <= nums[mid])
            {
                // Left side is sorted
                if (nums[left] <= target && target < nums[mid])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                // Right side is sorted
                if (nums[mid] < target && target <= nums[right])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }

        // If the target is not found
        return -1;
    }

    public static void Main(string[] args)
    {
        SearchRotatedSortedArray search = new SearchRotatedSortedArray();

        // Test cases
        Console.WriteLine(search.Search(new int[] { 4, 5, 6, 7, 0, 1, 2 }, 6));  // Output: 2
        Console.WriteLine(search.Search(new int[] { 4, 5, 6, 7, 0, 1, 2 }, 0));  // Output: 4
        Console.WriteLine(search.Search(new int[] { 4, 5, 6, 7, 0, 1, 2 }, 3));  // Output: -1
        Console.WriteLine(search.Search(new int[] { 1 }, 0));  // Output: -1
        Console.WriteLine(search.Search(new int[] { 1, 3 }, 3));  // Output: 1
    }
}

Output:

Explanation of the said C# code:

Function Definition (Search):

Input parameters:

An array of integers 'nums'.
An integer 'target' which is the value to search for.

Initialization:

Two pointers 'left' and 'right' are initialized to the start (0) and end (nums.Length - 1) of the array, respectively.

Binary search loop:

A "while" loop continues as long as 'left' is less than or equal to 'right'.

Middle Index calculation:

The middle index 'mid' is calculated as (left + right) / 2.

Target check:

If the 'target' is found at the 'mid' position, return 'mid'.

Determine the sorted side:

Check if the left side of the array (nums[left] to nums[mid]) is sorted.
If it is, determine if the 'target' lies within this sorted portion. Adjust 'right' pointer if 'target' is within this range; otherwise, adjust 'left' pointer.
If the left side is not sorted, then the right side ('nums[mid]' to 'nums[right]') must be sorted. Check if 'target' lies within this sorted portion. Adjust 'left' pointer if 'target' is within this range; otherwise, adjust 'right' pointer.

Return not found:

If the 'target' is not found after the loop ends, return -1.

JavaScript - Search in a Rotated Sorted Array

Code:

function search(nums, target) {
    // Initialize pointers for binary search
    let left = 0, right = nums.length - 1;

    while (left <= right) {
        // Find the middle index
        let mid = Math.floor((left + right) / 2);

        // Check if the target is at the mid position
        if (nums[mid] === target) {
            return mid;
        }

        // Determine which side is sorted
        if (nums[left] <= nums[mid]) {
            // Left side is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right side is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    // If the target is not found
    return -1;
}

// Test cases
console.log(search([4, 5, 6, 7, 0, 1, 2], 6));  // Output: 2
console.log(search([4, 5, 6, 7, 0, 1, 2], 0));  // Output: 4
console.log(search([4, 5, 6, 7, 0, 1, 2], 3));  // Output: -1
console.log(search([1], 0));  // Output: -1
console.log(search([1, 3], 3));  // Output: 1

Output:

Explanation of the said JavaScript code:

Function definition (search):

Input parameters:

nums: An array of integers.
target: An integer value to search for within the array.

Initialization:

Two pointers, 'left' and 'right', are initialized to the start (0) and end (nums.length - 1) of the array, respectively.

Binary search loop:

A "while" loop continues as long as 'left' is less than or equal to 'right'.

Middle index calculation:

The middle index 'mid' is calculated as Math.floor((left + right) / 2).

Target Check:

If the 'target' is found at the 'mid' position, return 'mid'.

Determine the Sorted Side:

Check if the left side of the array ('nums[left]' to 'nums[mid]') is sorted.
If it is sorted, determine if the 'target' lies within this sorted portion. If so, adjust the 'right' pointer to 'mid - 1'; otherwise, adjust the 'left' pointer to 'mid + 1'.
If the left side is not sorted, then the right side ('nums[mid]' to 'nums[right]') must be sorted. Check if the 'target' lies within this sorted portion. If so, adjust the 'left' pointer to 'mid + 1'; otherwise, adjust the 'right' pointer to 'mid - 1'.

Return Not Found:

If the 'target' is not found after the loop ends, return -1.

Time and Space Complexity:

Time Complexity:

The time complexity of the provided Python code can be analyzed by considering the nature of the binary search algorithm:

Binary Search Process:

In each iteration of the "while" loop, the search space is halved. This is because we adjust either the 'left' or the 'right' pointer based on whether the target lies in the left or right half of the current search space.
This halving of the search space in each iteration continues until the 'left' pointer exceeds the 'right' pointer, at which point the target is either found or confirmed to be absent from the array.

Number of Iterations:

In the worst case, the number of iterations required to either find the target or exhaust the search space is proportional to the logarithm of the number of elements in the array ('n'). This is due to the halving process described above.

Overall Time Complexity:

Therefore, the time complexity of the algorithm is O(logn), where 'n' is the number of elements in the array.

Space Complexity:

The space complexity of the provided Python code can be analyzed by considering the memory usage of the algorithm:

Auxiliary Space:

The algorithm uses a constant amount of extra space, regardless of the input size. This space is used for the variables 'left', 'right', 'mid', and a few additional variables for comparison and assignment operations.
No additional data structures that grow with the input size are used in this algorithm.

Overall Space Complexity:

Therefore, the space complexity of the algorithm is O(1), indicating constant space usage.