Algo.Java.BinarySearch

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
    }

}