Binary Search — Lower Bound, Upper Bound, and Rotated Array

import java.util.Arrays;

public class BinarySearchVariants {

    // Standard binary search
    static int binarySearch(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    // Lower bound — first index where arr[i] >= target
    static int lowerBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // Upper bound — first index where arr[i] > target
    static int upperBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // Count occurrences of target
    static int count(int[] arr, int target) {
        return upperBound(arr, target) - lowerBound(arr, target);
    }

    // Search in rotated sorted array
    static int searchRotated(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) return mid;

            if (arr[lo] <= arr[mid]) { // left half sorted
                if (target >= arr[lo] && target < arr[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else { // right half sorted
                if (target > arr[mid] && target <= arr[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }

    // Find peak element
    static int findPeak(int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < arr[mid + 1]) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // Binary search on answer (minimum capacity to ship within D days)
    static int shipWithinDays(int[] weights, int days) {
        int lo = Arrays.stream(weights).max().orElse(0);
        int hi = Arrays.stream(weights).sum();

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int needed = 1, current = 0;
            for (int w : weights) {
                if (current + w > mid) { needed++; current = 0; }
                current += w;
            }
            if (needed <= days) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    public static void main(String[] args) {
        int[] sorted = {1, 2, 2, 2, 3, 5, 8, 13};

        System.out.println("Search 2: " + binarySearch(sorted, 2));
        System.out.println("Lower bound 2: " + lowerBound(sorted, 2)); // 1
        System.out.println("Upper bound 2: " + upperBound(sorted, 2)); // 4
        System.out.println("Count of 2: " + count(sorted, 2));          // 3

        int[] rotated = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("Rotated search 0: " + searchRotated(rotated, 0)); // 4

        int[] peaks = {1, 3, 5, 4, 2};
        System.out.println("Peak at: " + findPeak(peaks)); // 2

        int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println("Min capacity for 5 days: " + shipWithinDays(weights, 5)); // 15
    }
}