算法总结

时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。

排序算法 平均时间复杂度 平均空间复杂度
二分查找 O(log2n) 递归：O(log2n)，非递归：O(1)

二分查找（Binary Search）

算法描述

  1. 首先元素队列要有序；
  2. 然后跟队列中间位置的比较，根据大小选择左或右队列，再次折半查找；
  3. 直到找到相同元素或无匹配。

代码实现

注：默认从小到大排序。

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
<?php

//递归
function BinarySearch($arr, $intV, $intL, $intR) {
    if ($intL > $intR) {
        return -1;
    }

    $intM = intval(($intL + $intR) / 2);
    if ($intV == $arr[$intM]) {
        return $intM;
    }
    else if ($intV < $arr[$intM]) {
        return BinarySearch($arr, $intV, $intL, $intM - 1);
    }
    else {
        return BinarySearch($arr, $intV, $intM + 1, $intR);
    }
}

//非递归
function BinarySearch2($arr, $intV, $intL, $intR) {
    while($intL <= $intR) {
        $intM = intval(($intL + $intR) / 2);
        if ($intV == $arr[$intM]) {
            return $intM;
        }
        else if ($intV < $arr[$intM]) {
            $intR = $intM - 1;
        }
        else {
            $intL = $intM + 1;
        }
    }
    return -1;
}

$arr = array(0,1,2,3,4,5,6,7,8);
$intI = BinarySearch($arr, 2, 0, 8);
//$intI = BinarySearch2($arr, 2, 0, 8);
var_export($intI);