Introduction

Binary search is a very efficient search algorithm, applicable to sorted data. However, in competitive programming, we often encounter problems involving variations of sorted arrays, such as rotated sorted arrays. A rotated sorted array is an array that was initially sorted, but then a portion of the array was moved from one end to the other. For example, [4, 5, 6, 7, 0, 1, 2] is a rotated sorted array derived from [0, 1, 2, 4, 5, 6, 7].

The challenge is to efficiently search for an element in this rotated array, leveraging the partially sorted nature to achieve better than linear time complexity. Adapting binary search is the key to solving these problems efficiently.

Applications of Binary Search in Rotated Sorted Arrays

Binary search, when adapted correctly, becomes a powerful tool for solving various problems involving rotated sorted arrays. Some key applications include:

• Searching for a specific element: The most common application is to find whether a given element exists in the rotated sorted array, and if so, return its index.
• Finding the minimum element: Rotated sorted arrays often require finding the smallest element. The location of this minimum element signifies the point of rotation.
• Counting occurrences of an element: While not directly solvable with plain binary search on a rotated array, we can find the boundaries of the element's range once we have adapted the binary search for the rotated array.

Adapting Binary Search for Rotated Sorted Arrays

The core idea behind adapting binary search is to maintain the binary search paradigm while being aware of the rotation. We need to determine which half of the array is sorted in each iteration, and then decide whether the target element lies within that sorted half. This is usually done by comparing the middle element with the leftmost and rightmost elements of the current search space.

Here's a breakdown of the adaptation process:

1. Initialization: Set left = 0 and right = array.length - 1.
2. Iteration: While left <= right:
   1. Calculate the middle index: mid = left + (right - left) / 2 (to avoid potential integer overflow).
   2. If array[mid] == target, return mid.
   3. Determine if the left half is sorted: If array[left] <= array[mid], then the left half (array[left] to array[mid]) is sorted.
      • If target >= array[left] && target < array[mid], the target lies in the left sorted half. Set right = mid - 1.
      • Otherwise, the target lies in the right unsorted half. Set left = mid + 1.
   4. Otherwise, the right half is sorted: If array[left] > array[mid], then the right half (array[mid+1] to array[right]) is sorted.
      • If target > array[mid] && target <= array[right], the target lies in the right sorted half. Set left = mid + 1.
      • Otherwise, the target lies in the left unsorted half. Set right = mid - 1.
3. Element not found: If the loop completes without finding the target, return -1.

Java Solutions for Competitive Programming

Searching for an Element in a Rotated Sorted Array

 import java.util.*;
import java.lang.*;
import java.io.*;


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

        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoid potential integer overflow

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

            // Determine if the left half is sorted
            if (nums[left] <= nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // The right half is sorted
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1; // Target not found
    }

      public static void main(String[] args) {
        Solution sol = new Solution();

        //Example usages
        int[] nums1 = {4, 5, 6, 7, 0, 1, 2};
        int target1 = 0;
        System.out.println("Index of " + target1 + " in nums1: " + sol.search(nums1, target1)); // Output: 4

        int[] nums2 = {4, 5, 6, 7, 0, 1, 2};
        int target2 = 3;
        System.out.println("Index of " + target2 + " in nums2: " + sol.search(nums2, target2)); // Output: -1

        int[] nums3 = {1};
        int target3 = 0;
        System.out.println("Index of " + target3 + " in nums3: " + sol.search(nums3, target3)); // Output: -1

        int[] nums4 = {5,1,3};
        int target4 = 5;
        System.out.println("Index of " + target4 + " in nums4: " + sol.search(nums4, target4)); // Output: 0
    }
} 

Finding the Minimum Element in a Rotated Sorted Array

 import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) { //changed from <= to < since returning nums[left]
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                // Minimum element is in the right half
                left = mid + 1;
            } else {
                // Minimum element is in the left half or is nums[mid] itself
                right = mid;
            }
        }

        return nums[left]; //When left == right this will be the minimum element
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        //Example usages
        int[] nums1 = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("Minimum in nums1: " + sol.findMin(nums1)); // Output: 0

        int[] nums2 = {3, 4, 5, 1, 2};
        System.out.println("Minimum in nums2: " + sol.findMin(nums2)); // Output: 1

        int[] nums3 = {11, 13, 15, 17};
        System.out.println("Minimum in nums3: " + sol.findMin(nums3)); // Output: 11

        int[] nums4 = {2,1};
        System.out.println("Minimum in nums4: " + sol.findMin(nums4)); // Output: 1
    }
}