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);
        }
    }

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;
    }