二叉树算法

相关链接

思维导图：https://kdocs.cn/l/sptprEzrCRMi

故事背景

试想一下，在一个保存100个联系人里面，我要想快速找到某一个人，最多需要多少次。因为通讯录是按照abcd依次排序，我只需要7次就可以命中。因为 log2 100 等于7

示例图

从给定的数字中，命中给定值（85）：1,2,6,8,9,10,15,19,35,49,60,61,70,85,90,99,100

PHP实现

<?php
// 二分查找法
function binSearch($arr, $search)
{
    $height = count($arr)-1;$low = 0;
    while ($low <= $height) {
    $mid = floor(($low + $height) / 2);//获取中间数
    if ($arr[$mid] == $search) {
      return $mid;//返回
    } elseif ($arr[$mid] < $search) {//当中间值小于所查值时，则$mid左边的值都小于$search，此时要将$mid赋值给
      $low $low = $mid + 1;
    } elseif ($arr[$mid] > $search) {//中间值大于所查值,则$mid右边的所有值都大于$search,此时要将$mid赋值给$height
      $height = $mid-1;
    }
  }
  return "查找失败";
}

// 顺序查找法
function seqSearch($arr, $k)
{
  foreach ($arr as $key => $val) {
    if ($val == $k) {
      return $key;
    }
  }
  return -1;
}// 测试

$arr=array(5,10,19,22,33,44,48,55,60,68);
// echo binSearch($arr,44).'<br/>';
// echo seqSearch($arr,44).'<br/>';