二分查找-递归
算法描述：二分查找法也称为折半查找法，它的思想是每次都与序列的中间元素进行比较。二分查找的一个前提条件是数组是有序的，假设数组array为递增序列，findData为要查找的数，n为数组长度，首先将n个元素分成个数大致相同的两半，取array[n/2]与将要查找的值findData进行比较，如果findData等于array[n/2]，则找到findData，算法终止；如果findData<array[n/2]，则只要在数组array的左半部分继续搜索findData；如果findData>array[n/2]，则只需要在数组array的右半部分继续搜索即可。这个“左半部分”、“右半部分”的确定，都需要两个参数：开始标记与结束标记，比如初始状态时，开始标记为下标0，结束标记为数组长度-1，序列的中间元素下标就是开始标记+结束标记/2。要转到左半部分的中间元素，仅需要将结束标记改为中间元素下标-1；要转到右半部分的中间元素，则需要将开始标记改为中间元素下标+1。

应用场景：从一个有序数组中快速定位目标元素的位置，因此常与排序算法一块使用.

二分查找-非递归

对于非递归算法，自然是要用到循环了，在循环中开始标记和结束标记不断改变，循环的判断条件就是开始标记是否在结束标记之前。若查找成功则返回中间元素标记，若查找失败则返回-1。所以非递归算法需要三个参数：数组起始地址、数组长度以及要查找的数字。

function bin_search($arr,$low,$high,$value) { 
    while($low<=$high) { 
        $mid=floor(($low+$high)/2); 
        if($value==$arr[$mid]) 
            return $mid; 
        elseif($value<$arr[$mid]) 
            $high=$mid-1; 
        else 
            $low=$mid+1; 
    } 
    return false; 
}

二分查找-非递归

对于递归算法，判断条件是一样的，在调用自身的过程中，要改变的参数要么是开始标记，要么是结束标记。所以对于递归算法，需要四个参数：数组起止地址、要查找的数字、开始标记与结束标记。

<?php
// 归并排序：
// 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
//执行时间 3.3000000000005E-5 微秒
function Merge(&$arr, $left, $mid, $right) { 
  $i = $left; 
  $j = $mid + 1; 
  $k = 0; 
  $temp = array(); 
  while ($i <= $mid && $j <= $right) 
  { 
    if ($arr[$i] <= $arr[$j]) 
      $temp[$k++] = $arr[$i++]; 
    else 
      $temp[$k++] = $arr[$j++]; 
  } 
  while ($i <= $mid) 
    $temp[$k++] = $arr[$i++]; 
  while ($j <= $right) 
    $temp[$k++] = $arr[$j++]; 
  for ($i = $left, $j = 0; $i <= $right; $i++, $j++) 
    $arr[$i] = $temp[$j]; 

    return $arr; 
}
function MergeSort(&$arr, $left, $right) 
{ 
  if ($left < $right) 
  { 
    $mid = floor(($left + $right) / 2); 
    MergeSort($arr, $left, $mid); 
    MergeSort($arr, $mid + 1, $right); 
    Merge($arr, $left, $mid, $right); 
  } 
  return $arr;
}
//二分查找-递归

function bin_search($arr,$low,$high,$value) { 
    if($low>$high) 
        return false; 
    else { 
        $mid=floor(($low+$high)/2); 
        if($value==$arr[$mid]) 
            return $mid; 
        elseif($value<$arr[$mid]) 
            return bin_search($arr,$low,$mid-1,$value); 
        else 
            return bin_search($arr,$mid+1,$high,$value); 
    } 
}

$arr = ['12','65','20','22','32','52','3'];

// 记录开始时间
$time_start = microtime();

$res = MergeSort($arr,0,6);

$position = bin_search($res,0,6,32);
echo "<pre>";
print_r($res);
print_r($position);
echo "</pre>";

// 记录结束时间
$time_end = microtime();
$time = $time_end - $time_start;
 // 输出运行总时间 
echo "执行时间 $time 微秒";