社内勉強会で二分探索法を書いてみた話

はじめに

今回は二分探索法によるサーチプログラムを書くという課題を若手社員と一緒にもくもく書いてみました。
ネット検索については答えそのものを調べない(コピペ/写経禁止)という制限の下OKとしました。

---

問題

1〜1000までの数値が順番に格納された配列Aから、任意の値Bを二分探索で取り出す

---

解法

今回は二分探索法を使うという前提がある為、全員が同じ方針でプログラムを書くことになりました。
簡単に二分探索法の手順を示すと下記の通りです。

1. 配列の中央に格納された値を取り出して、目的の値と比較する
2. 目的の値であれば返す
3. 目的の値より大きければ中央より前を次の探索対象とする(1に戻る)
4. 目的の値より小さければ中央より後ろを次の探索対象とする(1に戻る)

ただし、この文章をプログラムで書き表すにあたっては4つの方法が出てきたので、これを紹介しようと思います。

---

再帰　or ループ

今回もまずこの２種類の書き方が出てきました。
基本方針は前回記事と同じなのでご参照ください。

社内勉強会で比率計算を書いてみた話

ただし、今回は配列からの探索なので、実際に活用してみようと考えると配列のデータ数の上限は必ずしも決まっていないと思います。
実案件で利用してみようと思うのであれば、ループを使う方がより安心です。

---

追記

コメントで指摘いただきましたインデックスの計算方法によるオーバーフローにも注意が必要でした。

Wikipedia - 二分探索 - 実装上の間違い

コメントにも貼っていただいた上記のリンク先にある間違った実装をしてしまっていました。
インデックスを単純に足してしまうとオーバーフローの危険があるので、減算を利用してオーバーフローを回避するようにします。

正

lower + (upper - lower) / 2

誤

(upper + lower) / 2

---

配列操作 or インデックス

探索を進める方法としてはこの2種類の方法が出てきました。
文字での説明は難しいのでコードを載せます。

配列操作.kt

    var centerVal: Int = 0
    do{
        val center: Int = list.size / 2
        centerVal = list.get(center)

        list = if(centerVal > target) {
            list.dropLast(center)
        }else {
            list.drop(center)
        }
    }while(centerVal != target)
    return centerVal

インデックス.kt

    var centerVal: Int = 0
    do{
        val center: Int = (start + end) / 2
        centerVal = list.get(center)

        if(centerVal > target) {
            end = center
            continue
        }
        start = center
    }while(centerVal != target)
    return centerVal

それぞれこんな感じでしょうか。
whileの条件次第でdo-whileじゃなくてもよくなります。
見た目上は大した差はなく、お好みでということになりそうですが、配列操作は重い処理になるので避けた方が良いです。

---

コード例

以下は今回の問題を各言語で書いてもらったものを比較しやすいように書き換えたコードです。
上に記した通り、配列のインデックスを使い、ループで回しています。
今回はSwiftの参加者がいなかったのでSwiftはお休みです。

---

Kotlin

fun main(args: Array<String>) {
    val A = List<Int>(1000, { it + 1 })
    val B = 233
    println(binarySearch(A, B))
}

fun binarySearch(list: List<Int>, target: Int): Int{
    if(target < list.first() || list.last() < target) {
        return -1
    }
    
    var first = 0
    var last = list.size

    while(first + 1 != last) {
        val center = first + (last - first) / 2
        val centerVal = list.get(center)

        if(centerVal == target) {
            return centerVal
        }
        
        if(centerVal < target) {
            first = center
        }else {
            last = center
        }
    }

    return -1
}

---

PHP

<?php

function main() {
    $A = range(1, 1000);
    $B = 233;

    echo binarySearch($A, $B);
}

function binarySearch($list, $target)
{
    if ($target < $list[0] || end($list) < $target) {
        return -1;
    }

    $first = 0;
    $last = count($list);

    while($first + 1 !== $last) {
        $center = floor($first + ($last - $first) / 2);
        $centerVal = $list[$center];

        if($centerVal === $target) {
            return $centerVal;
        }

        if($centerVal < $target) {
            $first = $center;
        }else {
            $last = $center;
        }
    }

    return -1;
}

main();

---

JavaScript

const main = () => {
  const A = new Array(1000)
    .fill('a')
    .map((el, i) => i + 1)
  const B = 233

  console.log(binarySearch(A, B))
}

const binarySearch = (list, target) => {
  let first = 0
  let last = list.length

  if(target < list[first] ||list[last-1] < target) {
      return -1
  }

  while (first + 1 !== last) {
    const center = Math.floor(first + (last - first) / 2)
    const centerVal = list[center]

    if (centerVal === target) {
      return centerVal
    }

    if (centerVal < target) {
      first = center
    } else {
      last = center
    }
  }

  return -1
}

main()

---

Java

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        List<Integer> A = new ArrayList<Integer>()        {
            {
                for(int i = 1; i <= 1000; i++) {
                    add(i);
                }
            }
        };
        int B = 233;

        System.out.println(binarySearch(A, B));
    }

    private static int binarySearch(List<Integer> list, int target) {
        int first = 0;
        int last = list.size();

        if(target < list.get(first) ||list.get(last - 1) < target) {
            return -1;
        }

        while (first + 1 != last) {
            final int center = (int) Math.floor(first + (last - first) / 2);
            final int centerVal = list.get(center);

            if (centerVal == target) {
                return centerVal;
            }

            if (centerVal < target) {
                first = center;
            } else {
                last = center;
            }
        }

        return -1;
    }    
}

---

まとめ

• 再帰よりループを使う
• 配列操作は重いのでインデックスを活用する