首页 / 算法 / 算法笔记-二分查找

算法笔记-二分查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记-二分查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5581字，纯文字阅读大概需要8分钟。

内容图文

【二分查找】二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。 ? 二分查找是一种非常高效的查找算法，时间复杂度是 O(logn)。O(logn) 这种对数时间复杂度，是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级O(1) 的算法还要高效。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。 ? 使用循环和递归都可以实现二分查找。 ?? ??? ? 二分查找应用场景的局限性：

二分查找依赖的是顺序表结构，简单点说就是数组。（链表不可以）
二分查找针对的是有序数据。（如果数据没有序，我们需要先排序。）
数据量太大不适合二分查找。

? 四种常见的二分查找变形问题 1.查找第一个值等于给定值的元素 2.查找最后一个值等于给定值的元素 3.查找第一个大于等于给定值的元素 4.查找最后一个小于等于给定值的元素 ? 适用性分析 1.凡事能用二分查找解决的，绝大部分我们更倾向于用散列表或者二叉查找树，即便二分查找在内存上更节省，但是毕竟内存如此紧缺的情况并不多。 2.求“值等于给定值”的二分查找确实不怎么用到，二分查找更适合用在”近似“查找问题上。比如上面讲几种变体。 ?

<?php

/**
 * 二分查找 查找=find的元素
 * @param array $numbers
 * @param [type] $find
 */
function binarySearch(array $numbers, $find)
{
    $low = 0;
    $high = count($numbers) - 1;
    return search($numbers, $low, $high, $find);
}

function search(array $numbers, $low, $high, $find)
{
    /**
     * notice1 循环退出条件
     */
    if ($low > $high) {
        return -1;
    }

    /**
     * notice2 mid计算
     */
    $mid = $low + (($high - $low) >> 1);
    if ($numbers[$mid] > $find) {
        //notice3 high值更新
        return search($numbers, $low, $mid - 1, $find);
    } elseif ($numbers[$mid] < $find) {
        //notice4 low值更新
        return search($numbers, $mid + 1, $high, $find);
    } else {
        return $mid;
    }
}

/**
 * 求数字的平方根，保留6位小数
 * @param [type] $number
 */
function squareRoot($number)
{
    if ($number < 0) {
        return -1;
    } elseif ($number < 1) {
        $min = $number;
        $max = 1;
    } else {
        $min = 1;
        $max = $number;
    }
    $mid = $min + ($max - $min) / 2;
    while (getDecimalPlaces($mid) < 6) {
        $square = $mid * $mid;
        if ($square > $number) {
            $max = $mid;
        } elseif ($square == $number) {
            return $mid;
        } else {
            $min = $mid;
        }
        $mid = $min + ($max - $min) / 2;
    }
    return $mid;
}

/**
 * 计算数字小数点后有几位数字
 * @param [type] $number
 */
function getDecimalPlaces($number)
{
    $temp = explode('.', $number);
    return @strlen($temp[1]);
}

// 测试二分查找给定值
$numbers = [0, 1, 2, 3, 3, 4, 5, 6, 7, 9];
$find = 6;
echo binarySearch($numbers, $find);
echo "\n";

//测试求平方根
echo squareRoot(3);
echo "\n";

<?php

/**
 * 找到第一个=value的元素
 * @param array $numbers
 */
function findFirstEqual(array $numbers, $find)
{
    $length = count($numbers);
    $low = 0;
    $high = $length - 1;
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($numbers[$mid] > $find) {
            $high = $mid - 1;
        } else if ($numbers[$mid] < $find) {
            $low = $mid + 1;
        } else {
            /**
             * 如果是第一个元素，或之前一个元素不等于我们要找的值
             * 我们就找到了第一个=find的element
             */
            if ($mid == 0 || $numbers[$mid - 1] != $find) {
                return $mid;
            } else {
                $high = $mid - 1;
            }
        }
    }

    return -1;
}

/**
 * 找到最后一个=find的元素
 * @param array $numbers
 * @param [type] $find
 */
function findLastEqual(array $numbers, $find)
{
    $length = count($numbers);
    $low = 0;
    $high = $length - 1;
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($numbers[$mid] > $find) {
            $high = $mid - 1;
        } else if ($numbers[$mid] < $find) {
            $low = $mid + 1;
        } else {
            /**
             * 如果mid是最后一个元素的index
             * 或mid后一个元素!=我们要找的值
             * 则找到了最后一个=find的value
             */
            if ($mid == $length - 1 || $numbers[$mid + 1] != $find) {
                return $mid;
            } else {
                $low = $mid + 1;
            }
        }
    }

    return -1;
}

/**
 * 找到第一个大于等于find的元素
 * @param array $numbers
 * @param [type] $find
 */
function findFirstGreaterEqual(array $numbers, $find)
{
    $length = count($numbers);
    $low = 0;
    $high = $length - 1;
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($numbers[$mid] >= $find) {
            if ($mid == 0 || $numbers[$mid - 1] < $find) {
                return $mid;
            } else {
                $high = $mid - 1;
            }
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

/**
 * 找到最后一个小于等于find的元素
 * @param array $numbers
 * @param [type] $find
 */
function findLastLessEqual(array $numbers, $find)
{
    $length = count($numbers);
    $low = 0;
    $high = $length - 1;
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($numbers[$mid] <= $find) {
            if ($mid == $length - 1 || $numbers[$mid + 1] > $find) {
                return $mid;
            }
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return -1;
}


/**
 * 循环数组中找指定元素
 * @param array $numbers
 * @param [type] $find
 *
 * @return void
 * @date 2018/11/27
 * @author yuanliandu <yuanliandu@qq.com>
 */
function searchCircularArray(array $numbers, $find)
{
    $length = count($numbers);
    $low = 0;
    $high = $length - 1;

    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($numbers[$mid] === $find) {
            return $mid;
        }

        if ($numbers[$low] > $numbers[$mid]) {
            // 后半部分是有序数组
            if (($numbers[$mid] < $find) && ($numbers[$high] >= $find)) {
                if ($numbers[$high] === $find) return $high;
                //在后半个区间内
                $low = $mid + 1;
            } else {
                $high = $mid - 1;
            }
        } else {
            // 前半部分是有序的
            if (($numbers[$low] <= $find) && ($numbers[$mid] > $find)) {
                // 在有序区间内
                if ($numbers[$low] === $find) return $low;
                $high = $mid - 1;
            } else {
                $low = $mid + 1;
            }
        }

    }
    return -1;
}

/***
 * 测试
 */
$numbers = [1, 2, 3, 3, 3, 4, 5, 6, 8, 11, 13];
$find = 3;

var_dump(findFirstEqual($numbers, $find));//找到第一个等于find的元素,结果:2
var_dump(findFirstGreaterEqual($numbers, $find));//找到第一个大于等于find的元素,结果:2
var_dump(findLastEqual($numbers, $find));//找到最后一个=find的元素,结果:4
var_dump(findLastLessEqual($numbers, $find));//找到最后一个小于等于find的元素,结果:4


//测试在循环数组中找到指定数字
$numbers = [9, 10, 1, 2, 3, 4, 5, 6, 7, 8];
$find = 2;
var_dump(searchCircularArray($numbers, $find)); //结果:3

? ? ? ?

内容总结

以上是互联网集市为您收集整理的算法笔记-二分查找全部内容，希望文章能够帮你解决算法笔记-二分查找所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/842323.html

来源：【匿名】

【上一篇】插入排序-by-Python 【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【算法笔记-二分查找】教程文章相关的互联网学习教程文章

算法_欧几里得算法【代码】

求两个数的最大公约数,比如50和15的最大公约数是5,算法如下:# 欧几里得求最大公约数def gcd(m, n):while (n != 0):rem = m % nm = nn = remreturn m;# 测试 a = gcd(50, 15) print(a) 假设m>n ,第一次循环后,m替换成n,n则替换成余数rem,继续循环直到余数为0,返回最大公约数. 原文：https://www.cnblogs.com/coloz/p/11015812.html

C#彩色图片灰度化算法【代码】【图】

网上几种算法中速度相对较快的publicstatic Bitmap MakeGrayscale(Bitmap original) {//create a blank bitmap the same size as originalBitmap newBitmap = new Bitmap(original.Width, original.Height);//get a graphics object from the new imageGraphics g = Graphics.FromImage(newBitmap);//create the grayscale ColorMatrixSystem.Drawing.Imaging.ColorMatrix colorMatrix = new System.Drawing.Imaging.ColorMatrix(n...

103-算法应用【字符串反转】代码实现【代码】

字符串反转本文链接：https://www.cnblogs.com/cheng2839 介绍将字符串倒序组织分析我们都知道StringBuilder类有个reverse()方法，可以将字符串反转，但这里考察的是算法实现。所以我们采取链表存储字符串，然后将链表反转。实现下面是用java实现算法： //本文链接https://www.cnblogs.com/cheng2839publicclass $Convert {//反转方法publicstatic Entry convert(Entry root) {if (root == null)returnnull;Entry i = root, j = ...

Python -二叉树创建与遍历算法(很详细）【代码】

树表示由边连接的节点。它是一个非线性的数据结构。它具有以下特性。一个节点被标记为根节点。除根节点之外的每个节点都与一个父节点关联。每个节点可以有一个arbiatry编号的chid节点。我们使用前面讨论的os节点概念在python中创建了一个树数据结构。我们将一个节点指定为根节点，然后将更多的节点添加为子节点。下面是创建根节点的程序。创建树创建根我们只需要创建一个节点类并向节点添加赋值。这就变成了只有根节点的树。 1clas...

TCP慢启动算法【代码】【图】

慢启动定义慢启动，是传输控制协议使用的一种阻塞控制机制。慢启动也叫做指数增长期。慢启动是指每次TCP接收窗口收到确认时都会增长。增加的大小就是已确认段的数目。这种情况一直保持到要么没有收到一些段，要么窗口大小到达预先定义的阈值。如果发生丢失事件，TCP就认为这是网络阻塞，就会采取措施减轻网络拥挤。一旦发生丢失事件或者到达阈值，TCP就会进入线性增长阶段。这时，每经过一个RTT窗口增长一个段。慢启动解析发送方一...

HashMap与HashTable的哈希算法——JDK1.9源码阅读总结

下面是HashTable源码中的put方法：注意上面注释标注的地方：HashTable对于元素在哈希表中的坐标算法是：将对象自身的哈希值key.hashCode()变为正数：hash & 0x7FFFFFFF将上面得到的哈希值对表长取余，映射到哈希表中去。HashMap中哈希算法比HashTable中的稍微复杂一点。总体可以分为两步：一、重新计算key本身的哈希值上面代码中，首先是一个三目运算符，判断key是不是等于null，等于null，则返回0作为哈希值。否则，运算(h=key.ha...

C++ 算法【代码】【图】

C++ 算法算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法程序=数据结构+算法总结：算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据结构与算法相辅相成算法特...

A*算法研究【图】

许多工业与科学计算问题都可以转化为在图中寻路问题。启发式的寻路方法将问题表示为一个图，然后利用问题本身的信息，来加速解的搜索过程。一个典型的例子是有一些通路连接若干城市，找出从指定起点城市到指定终点城市的路径。但是有些问题不存在如此明显的事先定义好的图，它们的图是隐式图，也就是说，问题给定了搜索起点与一系列操作，对起点进行这些操作得到了它的后继结点，以及该操作的代价，对这些后继结点不断地重复操作，...

南邮算法分析与设计实验4 密码算法

南邮算法分析与设计实验4 密码算法实验目的了解现代密码学的基本原理和数论的基础知识，掌握非对称密码体制的著名代表RSA加密算法的工作原理和流程，并设计实现一个简单的密钥系统。实验内容了解加/解密的基本原理和工作过程，用公开密钥对明文进行加密，并用私人密钥对密文进行解密，构造一个简单的 RSA 公开密钥系统。实验原理 1、RSA算法是由麻省理工学院的 Ron Rivest,Adi Shamir 和Len Adleman 于 1977 年研制并于...

令牌桶限流算法和漏桶限流算法区别

1.漏桶限流算法的原理以固定速率从桶中流出水滴，以任意速率往桶中放入水滴，桶容量大小是不会发生改变的。流入：以任意速率往桶中放入水滴。流出：以固定速率从桶中流出水滴。水滴：是唯一不重复的标识。因为桶中的容量是固定的，如果流入水滴的速率>流出的水滴速率，桶中的水滴可能会溢出。那么溢出的水滴请求都是拒绝访问的，或者直接调用服务降级方法。前提是同一时刻。 2.令牌桶算法(Token) 令牌桶分为2个...

省选算法学习-矩阵与矩阵快速幂【代码】

0x00 引入矩阵，顾名思义，就是由数构成的矩形阵列比如这样的：$\begin{array}{l}\begin{bmatrix}2&3&4\0&7&13\c&\alpha&\sqrt5\end{bmatrix}\\end{array}$就是一个3*3的矩阵矩阵在信息学乃至数学里面的用处都非常广泛，下面就来介绍下它的一些基本知识，以及常用的地方。本文同时还会介绍矩阵快速幂以及快速矩阵乘法。0x01 何为矩阵矩阵的定义其实就是上面那样的啦......定义一个n行m列的矩阵为由n*m个数构成的矩形阵列，其中“数...

DotNet常用排序算法总结【代码】【图】

数据结构和算法对一个程序来说是至关重要的，现在介绍一下几种算法，在项目中较为常用的算法有：冒泡排序，简单选择排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序等7中算法。现在介绍选择排序算法，希尔排序算法，快速排序算法。 (1).选择排序算法：通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i(1大于等于i小于等于n)个记录交换。 (2).希尔排序：先取一个小于n的整数d1作为第一...

机器学习---算法学习3

词向量:将词语"嵌入"到一个N维空间，使得词语相近的词语放到相近的位置。机器翻译类不类似于矩阵的变换？谷歌出品的一个工具Word2Vec，用于入门。句向量？段向量？文档向量?很多事情向量化，可以解决很多问题。传统的one-hot 编码的原来是，有多少个字就有多少个维度.科[1,0,0,0,0,0,0,0]学[0,1,0,0,0,0,0,0]one hot -- >词向量表(全连接的大矩阵)-->输出(该词的矩阵)Embedding层就是one hot 层。时间序列:每次作预测都是一个序列...

算法导论学习笔记(2)－归并排序

今天学习了算法导论上的归并排序算法，并且完成了在纸上写出伪代码，以前就学过归并但是理解的不够透彻，以前还一直困惑：为什么明明归并排序比快排的时间复杂度更稳定，为什么库函数不用归并而用快排，现在知道原因了，因为归并排序必须开额外的空间，而且空间开销还比较大，下面介绍算法：首先，归并排序用到了分治的思想，把大数据分成若干个小数据，然后再分别对小数据进行处理，最后把小数据合并成大数据。其次，归并排序用到...

快速排序算法的 JavaScript 实现【代码】

快速排序是一种在大多数情况下比冒泡排序效率更高（详情参考有关算法复杂度的文章）的算法。注意：许多编程语言内置的排序 API 底层实现便是基于快速排序。ES5 与 ES6 语法在实现该算法时区别不大，以下仅提供 ES5 版本。function quickSort(arr) {var len = arr.length;if (len <= 1) {return arr.slice(0); // 注意用 slice 可防范 arr[0] 为 undefined }var left = [], right = [], mid = [];mid.push(arr[0]);for (var i = 1; ...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 算法笔记-二分查找

算法笔记-二分查找

内容导读

内容图文

内容总结

内容备注

内容手机端

【算法笔记-二分查找】教程文章相关的互联网学习教程文章

算法_欧几里得算法【代码】

C#彩色图片灰度化算法【代码】【图】

103-算法应用【字符串反转】代码实现【代码】

Python -二叉树创建与遍历算法(很详细）【代码】

TCP慢启动算法【代码】【图】

HashMap与HashTable的哈希算法——JDK1.9源码阅读总结

C++ 算法【代码】【图】

A*算法研究【图】

南邮算法分析与设计实验4 密码算法

令牌桶限流算法和漏桶限流算法区别

省选算法学习-矩阵与矩阵快速幂【代码】

DotNet常用排序算法总结【代码】【图】

机器学习---算法学习3

算法导论学习笔记(2)－归并排序

快速排序算法的 JavaScript 实现【代码】

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程