专栏首页网管叨bi叨二分查找算法速记

二分查找算法速记

二分查找(英语:binary search),也称折半搜索(英语:half-interval search)对数搜索(英语:logarithmic search,是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

适合的场景:

  • Sorted(单调递增或者递减)
  • Bounded (存在上下界,因为要一分为二的进行查找)
  • Accessible by index(能够通过索引访问)

时间复杂度:

  • O(logN)

空间复杂度:

  • O(N) 使用常数空间,无论任何大小的输入数据,算法使用的空间都是一样的

适用的数据结构:

数组,因为在内存中时连续的适合使用二分查找。但是链表不适合,因为链表坐标不是固定的,访问a[2]需要先从a[0]的后继节点找到a[1]再通过a[1]的后继节点才能访问到a[2]。

步骤:

  1. 初始状态left、right 分别指向数组的头和尾。
  2. 通过(left + right) /2 得到中间位置mid,访问数组中mid位置的元素。
  3. 判断其与查找目标的大小关系,相等则程序返回,
  4. 比目标小则挪动left指针到mid + 1;比目标大则挪动right指针到mid - 1
  5. 重复上面步骤2 ~ 4直到找到目标元素或者程序退出。

代码实现:

<?php
$list = [1, 2, 5, 6, 8, 9, 12, 15, 23, 32, 56, 67, 73, 85];
function bioSearch($list, $target){    $left = 0;    $right = count($list) - 1;    while ($left <= $right) {        $mid = ($left + $right) / 2;        if ($list[$mid] == $target) {            return true;        } else if ($list[$mid] < $target) {            $left = $mid + 1;            continue;        } else {            $right = $mid - 1;            continue;        }    }
    return false;}

本文分享自微信公众号 - 网管叨bi叨(kevin_tech),作者:KevinYan11

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 快速排序填坑口诀

    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此在很多笔试面试中出现的几率...

    KevinYan
  • 为什么Go的自定义error有时候会内存溢出

    分享一个在go tour上看到的练习题,练习里要求用户自己定义一个错误类型,实现 error接口,函数在参数不满足条件的时候返回自定义的错误类型的值。练习中特别...

    KevinYan
  • 用Golang构建gRPC服务

    继续之前,请确保你已经对gRPC概念有所了解,并且熟悉protocol buffer。需要注意的是教程中的示例使用的是 proto3版本的protocol bu...

    KevinYan
  • 算法导论第七章快速排序

    一、快速排序概述 关于快速排序,我之前写过两篇文章,一篇是写VC库中的快排函数,另一篇是写了快排的三种实现方法。现在再一次看算法导论,发现对快速排序又有了些新的...

    CloudDeveloper
  • 算法题目

    大学里的混子
  • 二分查找--查找重复有序数组中最左边的target

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • [PHP] 算法-统计一个数字在排序数组中出现的次数的PHP实现

    陶士涵
  • 二分法题型小结

    在刷题的过程中,二分法用的还是挺多的,有时候超时了往往是你没有用上二分法,今天我就来稍微总结下用的最多的三种二分法搜索。

    帅地
  • 127个常用的JS代码片段,每段代码花30秒就能看懂(六)

    大家好,今天我继续给大家分享本系列文章的最后一部分,感谢你对本系列文章的持续关注,希望对你的日常工作有所帮助。

    前端达人
  • Leetcode 852. Peak Index in a Mountain Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan

扫码关注云+社区

领取腾讯云代金券