【PHP】二分算法

<?php

class Binary
{
    private $executions = 0;
    private $type = '';
    //二分查找法
    public function binSearch($arr, $search)
    {
        $this->type = '非递归二分查找法';
        $height = count($arr)-1;
        $low = 0;
        while ($low <= $height) {
            $this->executions++;
            //获取中间数
            $mid = floor(($low + $height) / 2);
            // 判断当这个值等于寻找的那个值后直接返回
            if ($arr[$mid] == $search) {
                return $mid;
            //当中间值小于所查值时，则$mid左边的值都小于$search，此时要将$mid赋值给$low
            } elseif ($arr[$mid] < $search) {
                $low = $mid + 1;
            //中间值大于所查值,则$mid右边的所有值都大于$search,此时要将$mid赋值给$height
            } elseif ($arr[$mid] > $search) {
                $height = $mid-1;
            }
        }
        return "查找失败";
    }
    //顺序查找
    public function seqSearch($arr, $k)
    {
        $this->type = '顺序查找';
        foreach ($arr as $key => $val) {
            $this->executions++;
            if ($val == $k) {
                return $key;
            }
        }
        return "查找失败";
    }

    public function getCount()
    {
        return $this->type.' 执行了 '.$this->executions.'  次';
    }
}
$binary = new Binary;


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
 

<?php
require_once 'binary.php';
$arr = [1,2,3,4,5,6,7,8,9,10,11,12];
echo $binary->binSearch($arr, 19) ."\n";
echo $binary->getCount();

  

 

  
1
  
2
  
3
  
4
  
5
 

先把源码贴出来，然后在解析它

其实在经过几次debug你就可以发现，其实这边最重要的一个数值就是mid这个中间数
1.会先把中间数求出来
2.然后这个中间数会以索引值的形式存在
3.判断第一次这个索引值跟需要搜索的那个值是否相等
4.判断数组的这个中间数为索引的值是否比查询的小，如果小的话那就说明，这个中位数的索引的值 左侧都会小于这个搜索的值
5.判断数组的这个中间数为索引的值如果比查询的值大，那就说明这个中间数为索引的右侧都会比查询的这个值大
注意点：变量low跟height

文章来源: blog.csdn.net，作者：咔咔-，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/fangkang7/article/details/99573999