Binary Search and Its Variants in Java

Binary search is a fundamental algorithm that repeatedly compares the target key with the middle element of a sorted sub‑array, narrowing the search interval until the element is found or the interval is empty.

The article first presents a standard Java implementation of binary search that returns the index of the key or –1 if not found, emphasizing the importance of using the condition while (left <= right) to avoid infinite loops.

It then introduces several common variants, each with its own Java code:

Find the first element equal to the key.

Find the last element equal to the key.

Find the last element equal to or smaller than the key.

Find the last element smaller than the key.

Find the first element equal to or larger than the key.

Find the first element larger than the key.

Standard binary search implementation:

/**
 * 二分查找，找到该值在数组中的下标，否则为-1
 */
static int binarySerach(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == key) {
            return mid;
        } else if (array[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

Variant – find the first element equal to the key:

// 查找第一个相等的元素
static int findFirstEqual(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (left < array.length && array[left] == key) {
        return left;
    }
    return -1;
}

Variant – find the last element equal to the key:

// 查找最后一个相等的元素
static int findLastEqual(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] <= key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (right >= 0 && array[right] == key) {
        return right;
    }
    return -1;
}

Variant – find the last element equal to or smaller than the key:

// 查找最后一个等于或者小于key的元素
static int findLastEqualSmaller(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return right;
}

Variant – find the last element smaller than the key:

// 查找最后一个小于key的元素
static int findLastSmaller(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return right;
}

Variant – find the first element equal to or larger than the key:

// 查找第一个等于或者大于key的元素
static int findFirstEqualLarger(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Variant – find the first element larger than the key:

// 查找第一个大于key的元素
static int findFirstLarger(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

All variants share the same template: use while (left <= right) , compute mid = (left + right) / 2 , adjust left or right based on a comparison operator that reflects the desired boundary condition, and finally return either left or right depending on whether the algorithm should yield the leftmost or rightmost qualifying index.

Understanding how to choose the correct comparison ( < , <= , > , >= ) and which pointer to return is the key to implementing any binary‑search variant correctly.