返回首页 - Notes - 2013

二分查找


算法描述

本算法的 前提:目标数组一定要是按序排列的,这儿假设为从小到大排列

每次将数组平均分成两部分,将要查找的 关键字 与最中间的元素进行比较

如果 关键字 小于中间元素,则说明这个 关键字 一定在数组的左边部分,所以将查找范围的上限移动到中间下标以左,然后在新的范围内开始下一轮 二分

如果 关键字 大于中间元素,则说明这个 关键字 一定在数组的右边部分,所以将查找范围的下限移动到中间下标以右,然后在新的范围内开始下一轮 二分

如果 关键字 等于中间元素,则返回该中间元素的下标值,查找结束


算法实现

Ruby

# 二分
class Array
  def binary_search (key)
    lo, hi = 0, self.length - 1
    while lo <= hi
      mid = lo + (hi - lo) / 2
      hi = mid - 1 if key < self[mid]
      lo = mid + 1 if key > self[mid]
      return mid if key == self[mid]
    end
    -1
  end
end


# 测试
arr = (?a..?z).to_a
i = arr.binary_search ?e
printf '%d => %s' % [i, arr[i]] unless i == -1

PHP

<?php

// 二分
function binary_search ($arr, $key) {
    list($lo, $hi) = array(0, count($arr) - 1);
    while ($lo <= $hi) {
        $mid = intval($lo + ($hi - $lo) / 2);
        if ($key < $arr[$mid]) {
            $hi = $mid - 1;
        } elseif ($key > $arr[$mid]) {
            $lo = $mid + 1;
        } else {
            return $mid;
        }
    }
    return -1;
}


// 测试
$arr = range('a', 'z');
$i = binary_search($arr, 'e');
if ($i != -1) {
    echo "{$i} => {$arr[$i]}";
}

date : 2013-02-21、2014-11-22