算法——二分法查找（binarySearch）

素颜马尾好姑娘i 2021-11-26 15:04 370阅读 0赞

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

二分法查找的思路如下：

（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

二分法查找的时间复杂度O(logn)。

非递归算法：

function binarySearch(arr,key){ 
       var low= 0; //数组最小索引值 
       var high=arr.length -1; //数组最大索引值 
       while(low<=high){ 
       var mid= Math.floor((low+high)/ 2); 
       if(key==arr[mid]){ 
       return mid; 
       } else if(key>arr[mid]){ 
       low=mid+ 1; 
       } else{ 
       high=mid -1; 
       } 
       } 
       return -1; //low>high的情况，这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值 
       }

结果测试：

![SouthEast][]

递归算法：

function binarySearch(arr,low,high,key){ 
       if(low>high){ return -1;} 
       var mid= Math.floor((low+high)/ 2); 
       if(key==arr[mid]){ 
       return mid; 
       } else if(key<arr[mid]){ 
       high=mid -1; 
       return binarySearch(arr,low,high,key); 
       } else{ 
       low=mid+ 1; 
       return binarySearch(arr,low,high,key); 
       } 
       }

结果测试：

![SouthEast 1][]

[SouthEast]: /images/20211126/113e1fe995a247e9a3cc4bd72c9fb37c.png
[SouthEast 1]: /images/20211126/a4a2e107fd284191850bef9d40d702ee.png

发表评论取消回复

表情：

评论列表（有 0 条评论，370人围观）

还没有评论，来说两句吧...

相关阅读

相关二分查找算法模板-BinarySearch

分为两种： 1、二分找指定值 2、先逆二分找边界再二分找指定值 package com.xch1.binary; public class Ma

叁歲伎倆/ 2024年04月06日 10:26/ 0 赞/ 98 阅读

相关四种排序算法+二分法查找算法

1 四种排序算法 ①快速排序 ![这里写图片描述][SouthEast] / 快速排序（二分法排序） / class Qui

客官°小女子只卖身不卖艺/ 2024年02月17日 19:52/ 0 赞/ 92 阅读

相关【算法】【查找】二分法 Bisection

include<stdio.h> int main(){ int a[]={ 1,2,3,4,5,6,7,8,9,10

落日映苍穹つ/ 2023年10月10日 09:33/ 0 赞/ 73 阅读

相关二分法-binarySearch

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。二分法查找的思路如下：（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，

我不是女神ヾ/ 2023年07月09日 13:27/ 0 赞/ 17 阅读

相关查找算法——二分法

引言二分法，顾名思义，即一分为二的方法，通常用于判断在某个有序数列中是否存在某个数，由于其优秀的算法思想，时间复杂度一般都是 O(logN) ，通常要 O(N) 的遍历

傷城~/ 2022年11月13日 15:24/ 0 赞/ 278 阅读

相关算法二分查找法BinarySearch

算法二分查找法BinarySearch 1. 二分查找法概述 2. 二分查找法实现 1. 二分查找法概述二分查找也称折半查找（Binary Sea

谁借莪１个温暖的怀抱￠/ 2022年10月13日 12:34/ 0 赞/ 220 阅读

相关 JAVA-二分法查找算法总结

二分查找算法：二分查找算法也叫折半查找算法。优点：1.比较次数少 2.查找速度快 3.平均性能好缺点：1.待查表需要是有序的 2.插入、删除困难算法原理

ゞ浴缸里的玫瑰/ 2022年06月15日 02:58/ 0 赞/ 221 阅读

相关学习回顾算法（二分法查找）

二分法查找概述二分法查找也称为折半查找，属于有序查找算法。用给定值key先和中间结点的关键字比较，中间结点把线形表分成两个字表，若相等则查找成功；若不相等，再根据key

ゞ浴缸里的玫瑰/ 2022年06月04日 04:12/ 0 赞/ 244 阅读

相关 java搜索算法——二分法查找

java搜索算法——二分法查找搜索建立在排好序的基础之上 TestSearch.java //搜索算法 public class TestSear

待我称王封你为后i/ 2022年04月06日 09:24/ 0 赞/ 255 阅读

相关算法——二分法查找（binarySearch）

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。二分法查找的思路如下：（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束

素颜马尾好姑娘i/ 2021年11月26日 15:04/ 0 赞/ 371 阅读