1. 基础二分查找实现

在有序数组中查找特定元素的索引。这是二分查找最基本的形式，要求数组必须是升序排列。我们将分别展示迭代和递归两种实现方式。

迭代版本

public class BinarySearchUtil {
    public static int searchIterative(int[] data, int target) {
        int low = 0;
        int high = data.length - 1;

        while (low <= high) {
            // 使用无符号右移防止溢出
            int mid = (low + high) >>> 1;
            if (data[mid] == target) {
                return mid;
            } else if (data[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

递归版本

public class BinarySearchRecursive {
    public static int search(int[] data, int target) {
        return execute(data, 0, data.length - 1, target);
    }

    private static int execute(int[] arr, int start, int end, int val) {
        if (start > end) {
            return -1;
        }
        
        int pivot = start + ((end - start) >> 1);
        if (arr[pivot] == val) {
            return pivot;
        }
        return arr[pivot] > val 
            ? execute(arr, start, pivot - 1, val) 
            : execute(arr, pivot + 1, end, val);
    }
}

2. 寻找大于目标值的最小索引

该变种常用于寻找"上界"。即使数组中存在重复元素或目标值不存在，它也能返回第一个严格大于目标值的元素下标。

public static int findFirstGreater(int[] nums, int threshold) {
    int left = 0;
    int right = nums.length - 1;
    int index = -1;

    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > threshold) {
            index = mid; // 暂存可能的结果
            right = mid - 1; // 继续向左压缩区间
        } else {
            left = mid + 1;
        }
    }
    return index;
}

3. 寻找小于目标值的最大索引

该变种用于寻找"下界"，即数组中最后一个严格小于目标值的元素位置。

public static int findLastSmaller(int[] nums, int limit) {
    int low = 0;
    int high = nums.length - 1;
    int pos = -1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (nums[mid] < limit) {
            pos = mid; // 记录位置
            low = mid + 1; // 尝试向右寻找更大的索引
        } else {
            high = mid - 1;
        }
    }
    return pos;
}

4. 两个有序数组寻找第 K 小的元素

在不合并数组的情况下，利用二分思想在 O(log(m+n)) 时间复杂度内找到两个有序数组合并后的第 K 小元素。

public class KthElementFinder {
    public static int getKthSmallest(int[] a, int[] b, int k) {
        return find(a, 0, b, 0, k);
    }

    private static int find(int[] a, int aOffset, int[] b, int bOffset, int k) {
        // 边界处理：若数组已排除完毕
        if (aOffset >= a.length) return b[bOffset + k - 1];
        if (bOffset >= b.length) return a[aOffset + k - 1];
        
        if (k == 1) return Math.min(a[aOffset], b[bOffset]);

        // 选取每个数组的第 k/2 个元素进行比较
        int half = k / 2;
        int midA = (aOffset + half - 1 < a.length) ? a[aOffset + half - 1] : Integer.MAX_VALUE;
        int midB = (bOffset + half - 1 < b.length) ? b[bOffset + half - 1] : Integer.MAX_VALUE;

        if (midA < midB) {
            return find(a, aOffset + half, b, bOffset, k - half);
        } else {
            return find(a, aOffset, b, bOffset + half, k - half);
        }
    }
}

5. 旋转排序数组中的搜索

针对一个在某个点发生旋转的有序数组（如 [4,5,6,0,1,2]），通过判断中点落在哪一段有序区间来决定搜索方向。

public static int searchInRotatedArray(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;

    while (start <= end) {
        int mid = start + ((end - start) >> 1);
        if (nums[mid] == target) return mid;

        // 判断哪一部分是有序的
        if (nums[start] <= nums[mid]) {
            // 左半部分有序
            if (target >= nums[start] && target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        } else {
            // 右半部分有序
            if (target > nums[mid] && target <= nums[end]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return -1;
}