PHP half (bisection) search algorithm example analysis

This article mainly introduces the PHP half (two-point) search algorithm. It analyzes the concept, principle, implementation and usage of the PHP half-half (two-point) search algorithm in detail in the form of examples. It also comes with a PHP half (two-point) search algorithm. ) Search algorithm class for your reference. Friends who need it can refer to

. The example in this article describes the PHP half (bisection) search algorithm. Share it with everyone for your reference, the details are as follows:

Half query is only applicable to arrays, strings, etc. that have been sorted in positive or reverse order;

Algorithm:

First take the middle position of the array, if there is no middle position, then round down;

Fold it in half from the middle, judge the size, and enter the first half or the second half;

then Perform the same half-and-half query on the first half or the second half,

will not stop until the matching character is found (in this example, break is used, if it is placed in a function, just return)

The code implemented by php is as follows:

<?php
$arr = array(1,2,3,4,5,6,7,8,9,10);//数组
$key = 4;//要查询的关键字
$low = 0;//开始位的标志
$high = count($arr);//终止位的标志
while($low <= $high){//查询开始结束的条件
 $mid = floor(($low + $high)/2);//进行中间位置计算，向下取整
 if($arr[$mid] == $key){//查询成功
 echo $arr[$mid];
 break;//结束本页执行，函数可用return
 }elseif($arr[$mid] > $key){ //查询前半段，把结束标志移到中间位置前一位
 $high = $mid - 1;
 }else{ //查询后半段，把开始位置移到中间位置的后一位
 $low = $mid + 1;
 }
}
/*
运行结果：4
*/
?>

##Additional: Halving (bisection) search algorithm class:

/**
 * Description:php实现二分查找算法的类
 * @author wzy
 */
class binary_search{
  public $arr;
  public $key;
  function __construct($arr,$key){
    //这里初始化的数组已经是有序数组
    $this->arr=$arr;
    $this->key=$key;
  }
  function binarysearch(){
    $start=0;
    $end=count($this->arr)-1;
    while($start<=$end){
      //mid的取值可以为上整数或者下整数
      $mid=ceil(($start+$end)/2);
      //$mid=($start+$end)>>1;
      //$mid=intval(($start+$end)/2);
      if($this->arr[$mid]<$this->key){
        $start=$mid+1;
      }else if($this->arr[$mid]>$this->key){
        $end=$mid-1;
      }else{
        return $mid;
      }
    }
  }
}

You may also encounter this situation. The elements in the array have duplicate data, and the first one in the duplicate data needs to be returned. The position of an element, for example

$arr=array(1,2,3,4,5,6,6,6,6,7,8);

When searching for the element 6, the position returned should be 5, not others (the subscript starts counting from 0), so It needs to be judged on the returned mid. The code is as follows:

/**
 * Description:php实现二分查找算法的类
 * @author wzy
 */
class binary_search{
  public $arr;
  public $key;
  function __construct($arr,$key){
    //这里初始化的数组已经是有序数组
    $this->arr=$arr;
    $this->key=$key;
  }
  function binarysearch(){
    $start=0;
    $end=count($this->arr)-1;
    while($start<=$end){
      //mid的取值可以为上整数或者下整数
      $mid=ceil(($start+$end)/2);
      //$mid=($start+$end)>>1;
      //$mid=intval(($start+$end)/2);
      if($this->arr[$mid]<$this->key){
        $start=$mid+1;
      }else if($this->arr[$mid]>$this->key){
        $end=$mid-1;
      }else{
        //返回第一个匹配的元素
        for($i=$mid-1;$i>=0;$i--){
          if($this->arr[$i]==$this->key){
            $mid=$i;
          }else{
            break;
          }
        }
        return $mid;
      }
    }
  }
}

# #

The above is the detailed content of PHP half (bisection) search algorithm example analysis. For more information, please follow other related articles on the PHP Chinese website!