704. 二分探索

× 復習時の重要ポイント

1. midの計算時にint mid = left + (right - left) / 2;を使用して、int mid = (left + right) / 2;による整数オーバーフローを防ぐ必要がある
2. 通常の検索、左境界、右境界はすべて左閉じ右閉じ区間を使用可能。閉区間のright = arr.length-1と開区間のright = arr.lengthの違い、およびwhileループでの<=と<の使い分けに注意
3. 3種類の検索方法において、ループ内でarr[mid]==targetの場合の処理に注意
4. 3種類の検索方法の最後にarr[left]またはarr[right]をチェックする前に、leftとrightが境界を超えていないか確認すること。左側はarr.length、右側は-1かどうかをチェック

public int binarySearch(int[] data, int target) {
    int start = 0;
    int end = data.length - 1;

    while (start <= end) {
        int center = start + (end - start) / 2;
        if (data[center] == target) {
            return center;
        } else if (data[center] > target) {
            end = center - 1;
        } else {
            start = center + 1;
        }
    }
    return -1;
}

27. 要素の削除

√ 自分の解法はケースごとに分岐し、左右の二重ポインタを使用。個人的には理解しやすいが、コードが少し複雑になる

1. 左側が一致、右側が一致
2. 左側が一致、右側が不一致
3. 左側が不一致、右側が一致
4. 左側が不一致、右側が不一致

public int removeElement(int[] values, int removeValue) {
    int front = 0;
    int back = values.length - 1;
    while (front <= back){
        // 1.左側が一致、右側が一致
        // 2.左側が一致、右側が不一致
        // 3.左側が不一致、右側が一致
        // 4.左側が不一致、右側が不一致
        if (values[front] == removeValue){
            if (values[back] == removeValue){
                back--;
            } else {
                values[front] = values[back];
                front++;
                back--;
            }
        } else {
            if (values[back] == removeValue){
                back--;
            } else {
                front++;
            }
        }
    }
    return front;
}

ラブラドンの快慢ポインタ学習

class Solution {
    public int removeElement(int[] elements, int target) {
        int rapid = 0, slow = 0;
        while (rapid < elements.length) {
            if (elements[rapid] != target) {
                elements[slow] = elements[rapid];
                slow++;
            }
            rapid++;
        }
        return slow;
    }
}