钛节点

基础查找之二分查找

发表@2018-09-13 09:15:22

更新@2023-01-21 22:47:40

其实，有为青年在参与陌生商品价格竞猜节目的时候，是有技巧的。一贯场景可能都是这样的：

- 拿着话筒的主持人

![](https://ti-node.com/static/upload/6415022047126093825)

- 高端的不锈钢不粘锅

![](https://ti-node.com/static/upload/6415022327754391552)

- 有为青年

![](https://ti-node.com/static/upload/6415022494087905281)

一般情况下，游戏规则是有为青年在规定时间内猜测这个商品的价格，最后猜到的价格离这个商品的真实价格越近越好，越近奖励越丰厚，最后大奖就是把这个铁锅抱回家。

所以，在经过女主持人一顿操作后，竞猜开始：
有为青年：“500！”
女主持人：“高了”
有为青年：“250！”
女主持人：“高了”
有为青年：“125！”
女主持人：“低了”
有为青年：“ ( 125 + 250 ) / 2！”
女主持人：“高了！”
有为青年：“ ( 125 + ( 125 + 250 ) / 2 ) / 2！”
女主持人：“中了！”

作为普通青年，我们学习一下有为青年这种风骚的操作手法：也就是比较有名的二分查找。当然了，作为二分查找，是有一个前提的，那就是要查找的数据列表本身就是有序才行，不然，这个东西并没有什么卵用。

道理是比较简单浅显易懂粗俗不堪，下面，我们通过手敲代码来感受一下：

```php
<?php
$arr = [ 1,3,5,6,7,8,9,10,11,12,13,34,55,77,88,99,111,112,222,333 ];

// 我们要从 arr 中找到 data
function find( $arr, $data ){
  // 起始位置偏移量
  $begin_index = 0;
  // 末尾位置偏移量
  $end_index = count( $arr ) - 1;
  // 进入循环 终止条件是 当起始位置不再小于等于终止位置的时候
  while( $begin_index <= $end_index ){
    // 计算中间位置偏移量
    $mid_index = intval( ( $begin_index + $end_index ) / 2 );
    // 如果要找的值 比 中间位置的数值大
    if( $data > $arr[ $mid_index ] ){
      // 将起始位置偏移量更改为 中间位置+1
      $begin_index = $mid_index + 1;
    }   
    // 如果要找的值 比 中间位置的数值小
    else if( $data < $arr[ $mid_index ] ){
      // 将末尾位置偏移量更改为 中间位置-1
      $end_index = $mid_index - 1;
    }   
    // 如果等于了，也就是找到了
    else if( $data == $arr[ $mid_index ] ){
      return $mid_index;
    }   
  }
}
echo find( $arr, 6 );
echo PHP_EOL;
echo find( $arr, 5 );
echo PHP_EOL;
```

上述代码，值得注意的有两处：
- 11行，while循环的终止条件，这里务必注意，一定是有等号的
- 13行，中间位置的取值。可能会有同学觉着这里会不会漏过一些数据，实际上不会的，因为11行的约束。13行这里你甚至改成ceil或者floor都没有问题的

为什么突然这个时候冒出来一个二分查找呢？如果你仔细想想地话，上述查找过程就已经勾画出了一个二叉树，所以说，二分查找的时间复杂度是（logN）。因为二叉树我们前面好歹已经多多少少接触过一些了，所以引入二分查找就可以作为补充弥补一下了。