NullsArray

// Count how many nulls are in an array using binary search

public class NullsArray {

    public static void main(String[] args) {
        String[] stringArr = {"ant", null, null, "ball", null, null, null, "drive", null, null,
                "food"};
        String[] stringArr2 = {"ant", "drive", null, "food"};

        for (int i = 0; i < stringArr.length; i++) {
            System.out.println(stringArr[i]);
        }

        System.out.println(binarySearchWithNulls(stringArr, "drive"));
    }

    public static int binarySearchWithNulls(String[] words, String target) {
        int first = 0;
        int last = words.length-1;
        while (first <= last) {
            // skips nulls on either end of the list;
            if (words[first] == null) first++;
            else if (words[last] == null) last--;
            else {
                int mid = (last + first)/2;
                // if mid is null, move mid index to the left
                while (words[mid] == null && mid >= first) {
                    mid--;
                }
                if (words[mid].equals(target)) {
                    return mid;
                } else if (words[mid].compareTo(target) > 0) {
                    last = mid - 1;
                } else {
                    first = (last + first)/2 + 1;
                }
            }
        }
        return -1;
    }

}