---
title: 二分探索復習
tags: []
categories: ["Programming", "Algorithm", "BinarySearch"]
date: 2014-03-05T15:43:23Z
updated: 2014-03-05T15:43:23Z
---

二分探索の復習。`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]));
            }
        }
    }