js binary search algorithm
2024-10-19 06:00:56
js binary search algorithm
js 二分查找算法
二分查找, 前置条件
- 存储在数组中
- 有序排列
理想条件: 数组是递增排列，数组中的元素互不相同;
重排 & 去重
顺序: 递增排列/递减排列;
重复: 数组中存在相同的元素;
"use strict";
/**
*
* @author xgqfrms
* @license MIT
* @copyright xgqfrms
* @created 2020-05-20
* @modified
*
* @description 二分查找 binary-search
* @augments
* @example
* @link
*
*/
const log = console.log;
function binarySearch(data, key, preIndex = 0, debug = false){
let len = data.length;
// 向下取整
let half = Math.floor(len/2);
// 差值
let diffValue = key - data[half];
if(debug) {
// preIndex 保留上次的索引值 indexOf
log(`\npreIndex`, preIndex)
log(`len`, len)
log(`half`, half)
log(`key`, key)
log(`data[half]`, data[half])
// number - undefined == NaN
log(`diffValue`, diffValue)
}
if (diffValue > 0) {
preIndex = preIndex + half + 1;
let right = data.slice(half + 1);
return binarySearch(right, key, preIndex);
} else if (diffValue < 0) {
let left = data.slice(0, half);
return binarySearch(left, key, preIndex);
}else if (diffValue === 0) {
return preIndex + half;
} else {
return -1;
}
}
let v4 = binarySearch([1,3,5,7,9], 9);
log(`v4`, v4)
// 4
let v11 = binarySearch([1,3,5,7,9], 11);
log(`v11`, v11)
// -1
// binarySearch(5, [1,2,3,4,5,6,7,8]);
// // 4
// binarySearch(5, [1,3,5,7,9]);
// // 2
// binarySearch(1, [1,3,5,7,9]);
// // 0
// binarySearch(7, [1,3,5,7,9]);
// // 3
// binarySearch(9, [1,3,5,7,9]);
// // -1
BST
function binarySearch(target,arr,start,end) {
if( start > end){
return -1
}
var start = start || 0;
var end = end || arr.length-1;
var mid = parseInt(start + (end-start)/2);
if(target==arr[mid]){
return mid;
}else if(target>arr[mid]){
return binarySearch(target, arr, mid+1, end);
}else{
return binarySearch(target, arr, start, mid-1);
}
return -1;
}
binarySearch(9,[1,2,3,4,5,7,8])
// -1
https://www.jianshu.com/p/eef65b21ace0
Big O
xgqfrms 2012-2020
www.cnblogs.com 发布文章使用：只允许注册用户才可以访问！
最新文章
- python中使用heapq查看最大与最小的N个元素列表
- 《Qt Quick 4小时入门》学习笔记3
- Android项目:proguard混淆第三方jar.
- rabbitMQ 远程访问
- POJ 3174 Alignment of the Planets (暴力求解)
- 支持HTML5 SqlLite的AndroidApp
- schema文件中cube的事实表使用视图方法
- Android开发学习之路--Android Studio cmake编译ffmpeg
- kettle查询-2
- LeetCode【83. 删除排序链表中的重复元素】
- python算法双指针问题：使用列表和数组模拟单链表
- python isinstance()方法的使用
- 分散的配置文件VS集中的注册表
- Demo003 最大连续子数组问题（《算法导论》4.1-5）
- 〖Linux〗穿越城墙之后，直接连接国内网站的路由配置
- rsync配置及优化
- MySQL查看所有视图的命令
- 关于clear与清除浮动
- Mac OS Yosemite(10.10.3)系统下环境配置
- P145MathTool测试类的编写