Search in Rotated Sorted Array

class Solution {
public:
    int binarySearch(vector<int>& arr, int searchVal) {
        int size = arr.size();
        int start = 0, end = size - 1;
        while (start <= end) {
            int middle = start + (end - start) / 2;
            if (arr[middle] == searchVal) {
                return middle;
            }
            else if (arr[middle] >= arr[start]) {
                if (searchVal >= arr[start] && searchVal < arr[middle]) {
                    end = middle - 1;
                } else {
                    start = middle + 1;
                }
            }
            else {
                if (searchVal <= arr[end] && searchVal > arr[middle]) {
                    start = middle + 1;
                } else {
                    end = middle - 1;
                }
            }
        }
        return -1;
    }
};

In this solution to the problem of searching in a rotated sorted array using C++, you implement a modified binary search algorithm that adapts to the breakpoint where the sorting order is disrupted. The main idea revolves around dividing the array into potentially sorted subsections and then locating the target value within the appropriate subsection.

• Start by defining the binarySearch function that takes a reference to an integer vector and the target search value as parameters.
• Initialize variables start and end to define the current search range within the array, starting from the first to the last index.
• Use a while loop to repeatedly narrow down the search range:
  • Calculate the middle index of the current range.
  • If the value at the middle index matches the target value, return this index as the result.
  • Determine which half of the array is sorted:
    • If the left half from start to middle is sorted:
      • Check if the target is within this range. If true, adjust end to narrow down the search to this half. Otherwise, search in the other half by adjusting start.
    • If the left half isn't sorted, implying the right half must be:
      • Check if the target falls into the sorted right half and adjust start or end accordingly to focus the search.
• If the loop exits without finding the target value, return -1 indicating the target isn't present in the array.

This approach maintains a logarithmic time complexity similar to a regular binary search but adds conditions to handle the peculiarities of searching within a rotated sorted structure.

class SearchAlgorithm {
    public int binarySearch(int[] array, int goal) {
        int length = array.length;
        int start = 0, end = length - 1;
    
        while (start <= end) {
            int middle = start + (end - start) / 2;
    
            if (array[middle] == goal) {
                return middle;
            }
            else if (array[middle] >= array[start]) {
                if (goal >= array[start] && goal < array[middle]) {
                    end = middle - 1;
                } else {
                    start = middle + 1;
                }
            }
            else {
                if (goal <= array[end] && goal > array[middle]) {
                    start = middle + 1;
                } else {
                    end = middle - 1;
                }
            }
        }
    
        return -1;
    }
}

The provided Java code implements a solution for searching an element in a rotated sorted array using a modified binary search algorithm. Below summarizes the solution approach used in the code:

• The method binarySearch takes two parameters: an array of integers array and the integer goal, which is the target to find in the array.
• The binary search starts by initializing two pointers, start at index 0 and end at array.length - 1.
• Inside a while loop that continues as long as start is less than or equal to end:
  • Calculate the middle index middle using the start and end indices.
  • Check if the element at the middle index matches the target (goal). If it matches, return the index middle.
  • Determine which half of the array to search in:
    • If the element at the middle index is greater than or equal to the element at the start index, then the left half is sorted. Check if the target is within the range from start to middle; if so, focus the search on this half by adjusting the end pointer.
    • Otherwise, the right half must be sorted. Check if the target falls between the middle index and end index; adjust the start pointer accordingly.
• If the target is not found in any iteration, return -1 indicating the target is not present in the array.

This approach ensures log(n) complexity by continually halving the search space and is particularly optimized for searching in an array that has been rotated from a sorted position.

int binary_search_rotated(int* array, int size, int key) {
    int start = 0, end = size - 1;
    while (start <= end) {
        int middle = start + (end - start) / 2;
        if (array[middle] == key) return middle;
        else if (array[middle] >= array[start]) {
            if (key >= array[start] && key < array[middle])
                end = middle - 1;
            else
                start = middle + 1;
        }
        else {
            if (key <= array[end] && key > array[middle])
                start = middle + 1;
            else
                end = middle - 1;
        }
    }
    return -1;
}

This solution efficiently handles the problem of finding an element in a rotated sorted array using a modified version of binary search implemented in C.

Function binary_search_rotated takes three parameters:

• array - pointer to the first element of the array
• size - number of elements in the array
• key - the target value to search for within the array

Understand these key steps taken by the implementation:

1. Initialize start to 0 and end to size - 1.
2. Execute a while loop that continues as long as start is less than or equal to end.
3. Determine the middle of the current subarray with int middle = start + (end - start) / 2.
4. Check if the middle element is the key. If it is, return the index middle.
5. If the middle element is not the key, check if the left half of the array is sorted. This is done by comparing array[middle] with array[start].
6. Based on the sorted half of the array, adjust the start and end pointers. If the left half is sorted and the key is within the range of start and middle, narrow the search to the left half by setting end to middle - 1. Otherwise, adjust the search to the right half by setting start to middle + 1.
7. Similar adjustments are made if the right half is sorted.
8. If the key is not found in the array after exhausting the search space, return -1.

This function is robust and efficient, capable of handling arrays where the content has been shifted, keeping the search process within O(log n) time complexity due to its binary search nature.

var binarySearch = function (elements, value) {
  let length = elements.length;
  let start = 0,
      end = length - 1;
  while (start <= end) {
      let middleIndex = start + (((end - start) / 2) | 0);
      if (elements[middleIndex] == value) return middleIndex;
      else if (elements[middleIndex] >= elements[start]) {
          if (value >= elements[start] && value < elements[middleIndex]) end = middleIndex - 1;
          else start = middleIndex + 1;
      }
      else {
          if (value <= elements[end] && value > elements[middleIndex]) start = middleIndex + 1;
          else end = middleIndex - 1;
      }
  }
  return -1;
};

The JavaScript function binarySearch provided above efficiently searches for a specific value within a rotated sorted array. The function implements a modified version of binary search to adapt to the nuances of a rotated array where the first part of the array is rotated to the end. Here's a breakdown of its logic and operation:

• Initialize three pointers: start, end to represent the range still in play for search, and middleIndex to find the middle element within the current range.

• Run a while loop until the start pointer is less than or equal to the end pointer, indicating that there are still elements to check:

  • Calculate middleIndex using the average of start and end, adjusting for integer division.
  • Compare the element at middleIndex with the target value (value):
    • If a match is found, return middleIndex, signaling the position of the value in the array.
    • If no match is found, adjust the start and end pointers:
      • If the value at middleIndex is greater than or equal to the value at start, it indicates that the left half is sorted normally.
        • If the target value lies between start and middleIndex, narrow the search to the left half by adjusting end.
        • Otherwise, shift focus to the right half by adjusting start.
      • If the previous condition isn't met, the right half must be normally sorted.
        • If the target value lies between middleIndex and end, narrow the search to the right half by adjusting start.
        • Otherwise, focus on the left half by adjusting end.

• If the loop completes without finding the value, return -1 to indicate the value is not present in the array.

This function ensures optimal search even in a rotated array by adjusting search boundaries intelligently based on sorted segments. It retains a time complexity of O(log n), making it efficient for large datasets.

class Solution:
    def binary_search(self, array: List[int], key: int) -> int:
        # Initial indices setup
        low, high = 0, len(array) - 1
    
        while low <= high:
            midpoint = low + (high - low) // 2
                
            # Check if key is present at midpoint
            if array[midpoint] == key:
                return midpoint
    
            # If left side is sorted
            elif array[midpoint] >= array[low]:
                if key >= array[low] and key < array[midpoint]:
                    high = midpoint - 1
                else:
                    low = midpoint + 1
    
            # Right side must be sorted
            else:
                if key <= array[high] and key > array[midpoint]:
                    low = midpoint + 1
                else:
                    high = midpoint - 1
    
        # Key not found
        return -1

The provided Python solution implements a search in a rotated sorted array using a modified binary search algorithm, enhancing typical binary search to handle the rotation.

• Implement a search within the binary_search method that accepts array and key as parameters. It returns the index of the key if found, otherwise -1.
• Begin the search by initializing low to the start of the array and high to the end.
• A while loop continues until low exceeds high. Calculate the midpoint inside the loop.
• Check if the key is at the midpoint; return the index if true.
• Determine which segment of the array is sorted:
  • If the left segment is sorted and the key lies within this segment, adjust the high pointer.
  • Otherwise, adjust the low pointer to search in the right segment.
• If the key is not present in the array, the method returns -1 after the loop concludes.

This algorithm efficiently finds the position of the given key in logarithmic time, despite the initial array being rotated. Its implementation leverages conditions to decide the continuation of the search in a specific segment based on sorted order and key location, ensuring the search is always directed towards the possible location of the key.