IK.AM

@making's tech note


二分探索復習

🗃 {Programming/Algorithm/BinarySearch}
🗓 Updated at 2014-03-05T15:43:23Z  🗓 Created at 2014-03-05T15:43:23Z   🌎 English Page

二分探索の復習。java.util.Arrays#binarySearchは検索対象の要素が複数あった場合、どれの位置を返すか保証しない。

最初の位置を返したい場合は、対象の要素が見つかっても右側のポインタを左に進め続け、ループを抜けたときの右側のポインタの位置が答え。

最後の位置を返したい場合は、対象の要素が見つかっても左側のポインタを右進め続け、ループを抜けたときの左側のポインタの位置が答え。

簡単そうで少し難しい。

import java.util.Arrays;

public class BinarySearch {
    // 最初の要素の位置を返す
    public static int binarySearch(int[] arr, int key) {
        int i = -1, j = arr.length - 1;
        while (i + 1 != j) {
            int m = i + (j - i) / 2;
            if (arr[m] < key) {
                i = m;
            } else {
                j = m;
            }
        }
        if (arr[j] == key) {
            return j;
        }
        return -1;
    }

    // 最後の要素の位置を返す
    public static int binarySearch2(int[] arr, int key) {
        int i = 0, j = arr.length;
        while (i + 1 != j) {
            int m = i + (j - i) / 2;
            if (arr[m] <= key) {
                i = m;
            } else {
                j = m;
            }
        }
        if (arr[i] == key) {
            return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 3, 3, 3, 3, 4, 5, 6};
        System.out.println(Arrays.binarySearch(arr, 3));
        System.out.println(binarySearch(arr, 3));
        System.out.println(binarySearch2(arr, 3));
    }
}

実行結果

5
2
7

応用編。配列が回転した場合。

public class BinarySearchCustomized {
    private static int find(int[] arr, int v, int i, int j) {
        if (j < i) {
            return -1;
        }
        int m = i + (j - i) / 2;
        if (arr[m] == v) {
            return m;
        } else if (arr[i] == v) {
            return i;
        } else if (arr[j] == v) {
            return j;
        }

        /*
        |---------------|--------------------|
        i                    m     ^         j
        |---------------|--------------------|
        i             ^      m               j
        |---------------|--------------------|
        i       m     ^     j
        */
        if (v > arr[m]) {
            if (arr[m] <= arr[j]) {
                if (v < arr[j]) {
                    return find(arr, v, m, j);
                } else {
                    return find(arr, v, i, m);
                }
            } else {
                return find(arr, v, m, j);
            }
        }

        /*
        |---------------|--------------------|
        i                  ^ m               j
        |---------------|--------------------|
        i       m         ^ j
        |---------------|--------------------|
        i    ^      m               j
        */
        if (v < arr[m]) {
            if (arr[m] <= arr[j]) {
                return find(arr, v, i, m);
            } else {
                if (v < arr[j]) {
                    return find(arr, v, m, j);
                } else {
                    return find(arr, v, i, m);
                }
            }
        }

        return -1;
    }

    public static int search(int[] arr, int v) {
        return find(arr, v, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {15, 16, 19, 20, 25, 30, 100, 200, 1, 2, 3, 4, 5, 7, 10, 11, 12, 14};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(search(arr, arr[i]));
        }
    }
}

✒️️ Edit  ⏰ History  🗑 Delete