二分探索の基本原則

閉区間方式を推奨します。データ量が少ない場合は線形探索が適切です。探索終了時、iはtargetより大きい最初の要素を指し、jはtargetより小さい最初の要素を指します。配列にtargetが存在しない場合、挿入位置はiとなります。

74. 二次元行列探索

行列内の目標値探索手法。単一行/列の境界条件に注意。

public class MatrixSearcher {
    public boolean findInMatrix(int[][] data, int goal) {
        int rows = data.length;
        int cols = data[0].length;
        int total = rows * cols;
        
        if (total == 1) return data[0][0] == goal;
        
        int low = 0, high = total - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int r = mid / cols;
            int c = mid % cols;
            
            if (data[r][c] > goal) high = mid - 1;
            else if (data[r][c] < goal) low = mid + 1;
            else return true;
        }
        return false;
    }
}

162. 極値検出

隣接要素比較による極値探索手法。勾配方向を利用。

public class PeakFinder {
    public int locatePeak(int[] values) {
        int left = 0, right = values.length - 1;
        while (left < right) {
            int center = left + (right - left) / 2;
            if (values[center] < values[center + 1]) left = center + 1;
            else right = center;
        }
        return left;
    }
}

33. 回転済み配列探索

部分的有序性を利用した回転配列探索。

public class RotatedSearcher {
    public int searchRotated(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) return mid;
            
            if (nums[mid] >= nums[start]) {
                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;
    }
}

34. 範囲境界探索

目標値の最初と最後の位置を二分探索で特定。

public class RangeLocator {
    public int[] findBounds(int[] nums, int target) {
        return new int[]{findFirst(nums, target), findLast(nums, target)};
    }
    
    private int findFirst(int[] nums, int target) {
        int pos = binaryLocate(nums, target);
        if (pos == nums.length || nums[pos] != target) return -1;
        return pos;
    }
    
    private int findLast(int[] nums, int target) {
        int pos = binaryLocate(nums, target + 1);
        int lastPos = pos - 1;
        if (lastPos < 0 || nums[lastPos] != target) return -1;
        return lastPos;
    }
    
    private int binaryLocate(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }
}

153. 回転配列最小値

回転済み配列における最小要素探索。

public class RotationMinFinder {
    public int findRotationMin(int[] values) {
        if (values.length == 1) return values[0];
        if (values[0] < values[values.length - 1]) return values[0];
        
        int minVal = values[0];
        int left = 0, right = values.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (values[mid] >= minVal) left = mid + 1;
            else {
                right = mid - 1;
                minVal = values[mid];
            }
        }
        return values[left];
    }
}

4. 二配列中央値探索

O(log(m+n))時間での中央値探索手法。

public class DualArrayMedian {
    public double findMedian(int[] arr1, int[] arr2) {
        int total = arr1.length + arr2.length;
        if (total % 2 == 1) return findKth(arr1, arr2, total / 2 + 1);
        else return (findKth(arr1, arr2, total / 2) + findKth(arr1, arr2, total / 2 + 1)) / 2.0;
    }
    
    private int findKth(int[] a, int[] b, int k) {
        int idxA = 0, idxB = 0;
        while (true) {
            if (idxA == a.length) return b[idxB + k - 1];
            if (idxB == b.length) return a[idxA + k - 1];
            if (k == 1) return Math.min(a[idxA], b[idxB]);
            
            int step = k / 2;
            int newA = Math.min(idxA + step, a.length) - 1;
            int newB = Math.min(idxB + step, b.length) - 1;
            
            if (a[newA] <= b[newB]) {
                k -= (newA - idxA + 1);
                idxA = newA + 1;
            } else {
                k -= (newB - idxB + 1);
                idxB = newB + 1;
            }
        }
    }
}