## 二分查找
二分查找可以针对一个已经排序好了的数据快速查找出元素的所在位置
```php
var_dump(get_value(10,[6,7,8,9,10]));
function get_value($value,$arr){
	$len = count($arr);
	$start =0;
	$end = $len;
	
	while ($start<=$end) {
		//计算中间的下标
		$middle = floor(($start+$end)/2);
		if($arr[$middle] == $value){
			return $middle;
		}elseif ($arr[$middle]<$value) {
			//说明查找的数据在右侧
			$start = $middle+1;
		}else{
			//说明查找的数据在左侧
			$end = $middle-1;
		}
	}
}

```
## 插入排序
对于给定的一组数据，初始时假设第一个元素自成一个有序的列，其他的元素为无序的序列，接着从第二个元素开始按照元素的大小将元素插入到已经有的序的序列中，直到最后一个为止
```php
var_dump(insert_sort([100,24,3,88,77,44]));
function insert_sort($arr){
	$len = count($arr);
	for ($i=1; $i < $len; $i++) { 
		//获取当前需要比较的元素
		$tmp = $arr[$i];
		//内层循环用于从已排序区域寻找待排序元素的插入位置
		for($j=$i-1;$j>0;$j--){
			$index++;
			// 最先将要插入的元素插入到最后，随着循环移位会插入到正确的位置
			if($tmp<$arr[$j]){
				$arr[$j+1] = $arr[$j];
				$arr[$j] = $tmp;
			}else{
				break;
			}
		}
	}
	return $arr;
}
```
对于上面的代码在每次插入数据到已经排序好的序列中需要将所有的已经排序好的序列进行遍历，此处可以使用二分查找的方式优化
## 二分查找配合快速插入排序
```php
var_dump(insert_sort2([100,24,3,88,77,44]));
function insert_sort2($arr){
	$len = count($arr);
	for ($i=1; $i < $len; $i++) { 
		$value = $arr[$i];//取出要插入的元素
		$start = 0;
		$end = $i-1;
		//二分查找计算出当前要插入的元素的位置
		while ($start<=$end) {
			$middle = floor(($start+$end)/2);
			if ($arr[$middle]<$value) {
				//说明查找的数据在右侧
				$start = $middle+1;
			}else{
				//说明查找的数据在左侧
				$end = $middle-1;
			}
		}
		for ($j=$i-1; $j>=$start; $j--) { 
			$arr[$j+1] = $arr[$j];
		}
		$arr[$start] = $value;
	}
	return $arr;
}

```

插入排序配合二分查找实现数据排序