19
2017
02

常用PHP算法以及应用场景-二分查找

二分查找-递归
算法描述:二分查找法也称为折半查找法,它的思想是每次都与序列的中间元素进行比较。二分查找的一个前提条件是数组是有序的,假设数组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 微秒";




« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。