Algo.Java.BinarySearch

// most optimal approach, from my experience, on leetCode example

package org.example;


import java.util.Arrays;

/**
 * https://leetcode.com/problems/maximum-number-of-groups-entering-a-competition/description/
 */
public class Main {
    public static void main(String[] args) {
        maximumGroups(new int[]{10, 6, 12, 7, 3, 5});
    }

    public static int maximumGroups(int[] grades) {
        Arrays.sort(grades);
        long n = grades.length;
        long lo = 1; // minimum one group
        long hi = n;

        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long sum = (mid * (mid + 1)) / 2; // arithmetic progression

            if (sum == n) { // early exit
                return (int) mid;
            } else if (g(n, sum)) { 
                hi = mid - 1; // decrease,  for [lo, hi] || hi = mid for [lo, hi)
            } else {
                lo = mid + 1; // increase
            }
        }

        return (int) lo - 1; // unstable here, sometimes lo, sometimes lo-1
    }

    private static boolean g(long n, long sum) {
        return sum >= n;
    }
}

inspired by this article

iterative

    private static int binarySearch(int[] nums, int target, int lo, int hi) {
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] >= target) {
                hi = mid - 1;  // for [lo, hi] || hi = mid for [lo, hi)
            } else {
                lo = mid + 1;
            }
        }

        if (lo >= 0 && lo < nums.length && nums[lo] == target) {
            return lo;
        }

        return -1; // Returns <hi + 1> if not found
    }

recursive

    private int binarySearchRecursive(int[] nums, int target) {
        return doBinarySearchRecursive(nums, target, 0, nums.length - 1);
    }

    private int doBinarySearchRecursive(int[] nums, int target, int lo, int hi) {
        if (lo >= hi) {
            if (lo >= 0 && lo < nums.length && nums[lo] == target) {
                return lo;
            }

            return -1;
        }
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) {
            return doBinarySearchRecursive(nums, target, lo, mid - 1);
        } else {
            return doBinarySearchRecursive(nums, target, mid + 1, hi);
        }
    }

binary search for the array in descending order

    private static int binarySearchForDescArr(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] >= target) {
                lo = mid + 1; // changed here
            } else {
                hi = mid - 1; // and here
            }
        }

        if (hi >= 0 && hi < nums.length && nums[hi] == target) {
            return hi; // and returning hi
        }

        return -1;
    }

example from leetCode

https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/description/

    private static boolean g(int[] nums, int numIndex) {
        return nums[numIndex] < 0;
    }

    private static int getFirstNegativeBinary(int[] nums, int lo, int hi) {

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (g(nums, mid)) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        if (lo < nums.length && lo >= 0 && nums[lo] < 0) {
            return lo;
        }

        return -1;
    }

Sometimes we need EXACT BINARY SEARCH

/**
 * https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x/description/
 */
public class Main {
    public static void main(String[] args) {
        specialArray(new int[]{3, 6, 7, 7, 0});
    }

    public static int specialArray(int[] nums) {
        return binarySearch(nums);
    }

    private static int count(int[] nums, int mid) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= mid) {
                count++;
            }
        }
        return count;
    }

    /**
     * Sometimes we need exact count
     * 
     * @param nums 
     * @return
     */
    private static int binarySearch(int[] nums) {
        int lo = 0;
        int max = Arrays.stream(nums).max().getAsInt();
        int hi = max;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int count = count(nums, mid);

            if (mid == count) {
                return mid;
            }

            if (mid > count) {
                hi = mid - 1;  // for [lo, hi] || hi = mid for [lo, hi)
            } else {
                lo = mid + 1;
            }
        }

        return -1; // Returns <hi + 1> if not found
    }

}