二分查找法：又叫作折半查找法，它是在有序数组中查找指定数据的检索算法，比如一个数组（线性表）长度10万，查询某个数，二分查找首先把该线性表折半查询，找到这个中间位置对比看是不是，如果不是，再一次折半，重复搞下去，直到找到数据，每一次折半都踢出了一半的数据，不用一个一个对比找，所以查找效率相对高效。

两个条件：1：必须是线性表（数组），2：必须是有序存储。

算法：

left：数组开始位置；right：结束位置；mid：中间数（折半）；

mid = (left+right)/2

if mid对应的val（mid相当于数组的key）大于 要查找的val：数据在前半段查找，left不变，right = mid - 1

if mid对应的val（mid相当于数组的key）小于  要查找的val：数据在后半段查找，right不变，left = mid +1

如果 == 那么就找到了该值！

如果 left 大于 right，说明数据不存在。（如果不满足上面两个条件，也可能出现这种情况，数据在，但是查不到。）

举例：

首先定义一个数组：$list，数组中有17个元素，我们找出元素：7 的位置

$list[1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71]

第一次：
left 0
right 16 
mid (0+16)/2 = 8（折半）
这里mid = 8，对应上面的list[mid] = 14 因为 14 > 7：所以在前半段查找，left不变，right = mid - 1

第二次：
left 0
right (mid -1 ) = 7
mid (0+7)/2 = 3 (折半)
这里mid = 3，对应上面的list[mid] = 6 因为 6<7：所以在后半段查找，right不变，left = mid + 1

第三次：
left (mid+1) = 4
right 7
mid (7+4)/2 = 5（折半）
这里mid = 5，对应上面的list[mid] = 8 因为 8 >7 所以在半段查找，left不变，right = mid -1

第四次：
left 4
right (mid -1) 4
mid (4+4)/2= 4 (折半)
这里mid = 4，对应上面的list[mid] = 7 ，终于找到了数据。

php：算法：

<?php
$list = [1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71];

echo binarySearch($list,7); //找7的位置

function binarySearch($list,$val){
	if(!is_array($list)){
		return "存储结构非数组";
	}
	$count = count($list);// 数组长度
	$left = 0; //数组开始位置
	$right = $count - 1; //数组结束位置，从0开始，故减1
	while($left <= $right){
		$mid = intval(($left+$right)/2);//获取中间数取整
		if ($list[$mid] == $val){ //找到了
			return '数组元素7的key是:'.$mid;//返回数组的位置（key）
		}
		if ($list[$mid] > $val){
			$right = $mid - 1;
		} else {
			$left = $mid +1;
		}
	}
	return "数据不存在";
}

输出：数组元素7的key是:4

go写法：

package main
import (
    "fmt"
)

func main() {
    list := []int{1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71}
    key := binarySearch(&list,7)
    fmt.Println(key) //-1表示不存在
}

func binarySearch(arr *[] int,val int)int{
    left , right := 0 , len(*arr) -1 //起始位置
    for left <= right {
        mid := (left + right) / 2 //中间数
        if left > right {
            return -1
        }

        if (*arr)[mid] == val { 
            return mid
        }

        if(*arr)[mid] > val { 
            right = mid -1 
        }else{
            left = mid +1
        }
    }
    return -1
}