前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二分查找算法速记

二分查找算法速记

作者头像
KevinYan
发布2019-10-13 17:26:41
7700
发布2019-10-13 17:26:41
举报
文章被收录于专栏:网管叨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直到找到目标元素或者程序退出。

代码实现:

代码语言:javascript
复制
<?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;}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-04-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 网管叨bi叨 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档