二分法的原理和方法
最编程
2024-07-07 11:08:45
...
二分法查找原理及方法
二分法查找的思路如下:
1:首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。
2:如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤1的操作。
3:如果某一步数组为空,则表示找不到目标元素。
非递归方法
function binarySearch(arr,item){
var len = arr.length,
start = 0,
end = len-1;
while(start<=end){
var mid=Math.floor((start+end)/2);
if(item==arr[mid]){
return mid;
}else if(item>arr[mid]){
start = mid+1
}else{
end = mid-1
}
}
return arr;
}
var array=[1,3,4,8,10,33,66,88,90,110];
console.log(binarySearch(array,66));
递归
function binarySearch(arr,item,start,end){
var start = start || 0;
var end = end || arr.length-1;
if(start>end){
return false;
}
var mid=Math.floor((start+end)/2);
if(item==arr[mid]){
return mid;
}else if(item<arr[mid]){
return binarySearch(arr,item,start,mid-1);
}else{
return binarySearch(arr,item,mid+1,end);
}
}
var array=[1,3,4,8,10,33,66,88,90,110];
console.log(binarySearch(array,66,0,9));
上一篇: Java 常用的分段查找算法详细介绍
下一篇: 二分法的基础与实践
推荐阅读
-
C++ 中的抽象类和抽象方法
-
SpringCloud--持久层框架MyBatis Plus的使用方法和原理详解--V.MyBatis Plus 使用总结
-
Java HashMap 的数据结构和基本原理及其在 Jdk8、Jdk11 和 Jdk17 中的一些变化,以及一些常见问题。
-
力扣 1884.Egg Drop Two Egg(两个鸡蛋掉落) - 输入: n = 100 输出: 1414 解说 最佳策略是 - 从 9 楼扔下第一个鸡蛋。如果蛋碎了,那么 f 在 0 和 8 之间。从第 1 层扔第 2 个鸡蛋,然后每扔 1 层,分 8 次找到 f。总操作次数 = 1 + 8 = 9。 - 如果第一个鸡蛋没有破,那么从 22 楼扔第一个鸡蛋。如果蛋碎了,那么 f 介于 9 和 21 之间。将第二个鸡蛋从 10 楼往下扔,然后每扔一次往上扔一层楼,在 12 次尝试中找出 f。总操作次数 = 2 + 12 = 14。 - 如果第一个鸡蛋没有再次破碎,那么用类似的方法从 34、45、55、64、72、79、85、90、94、97、99 和 100 层扔第一个鸡蛋。 无论结果如何,最多需要扔 14 次才能确定 f。 一个非常有趣的问题 方法 1:动态编程
-
Spring Boot 异步任务、任务调度和异步请求线程池的用法和原理
-
MySQL 数据库的性能优化方法和途径有哪些?
-
使用 Redis 的分布式锁定原理、实现和优化
-
认证技术的原理和应用
-
[学习笔记] 利用多项式计算正弦和余弦近似值的快速方法。
-
背筋膜炎的症状和治疗方法