二分探索は効率的な検索アルゴリズムで、ソート済み配列に対する操作に適しています。基本的な実装パターンは以下の通りです：

int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return -1;
}

応用例1: H指数の計算

研究者の論文引用回数からH指数を計算します。H指数はh回以上引用された論文がh本以上ある最大の値です。

public int calculateHIndex(int[] citations) {
    int n = citations.length;
    int low = 0, high = n;
    while (low <= high) {
        int mid = (low + high) / 2;
        int count = 0;
        for (int c : citations) {
            if (c >= mid) count++;
        }
        if (count >= mid) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return high;
}

応用例2: 最小除数の探索

配列要素を指定された除数で割った合計が閾値以下になる最小の除数を見つけます。

public int findMinDivisor(int[] nums, int threshold) {
    int maxVal = Arrays.stream(nums).max().getAsInt();
    int left = 1, right = maxVal;
    while (left < right) {
        int mid = (left + right) / 2;
        int sum = 0;
        for (int num : nums) {
            sum += (num + mid - 1) / mid;
        }
        if (sum <= threshold) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

応用例3: 最長増加部分列

配列から要素の順序を保ったまま抽出できる最長の増加部分列の長さを求めます。

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int num : nums) {
        int i = 0, j = size;
        while (i != j) {
            int m = (i + j) / 2;
            if (tails[m] < num) {
                i = m + 1;
            } else {
                j = m;
            }
        }
        tails[i] = num;
        if (i == size) size++;
    }
    return size;
}

応用例4: 回転済み配列の検索

回転操作が施されたソート済み配列から要素を検索します。

public int searchRotatedArray(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) return mid;
        
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}