使用JS 实现二分法查找位置
【摘要】
使用二分法查找数值的位置:
前提是数组必须是有序的数组,
基本原理是:获取数组的中间值,与要查到的值x进行对比,中间值大于x,则继续对比中间值前半部分数组,依次类推
代码如下:
// 生成一个有序数组let createArr = () => { let arr = [] for(let i = 0; i ...
使用二分法查找数值的位置:
前提是数组必须是有序的数组,
基本原理是:获取数组的中间值,与要查到的值x进行对比,中间值大于x,则继续对比中间值前半部分数组,依次类推
代码如下:
-
// 生成一个有序数组
-
let createArr = () => {
-
let arr = []
-
for(let i = 0; i < 1000; i++){
-
arr.push(i)
-
}
-
return arr
-
}
-
let arr = createArr()
-
-
// 使用二分法查找一个值在有序数组中的索引位置
-
let findValueUseTwoSplit = (val, arr) => {
-
let start = 0
-
let end = arr.length - 1 // 获取最大索引
-
while (start <= end) {
-
debugger
-
let mid = Math.ceil((end+start) / 2) // 向上取整
-
console.log(`start:${start},mid:${mid},end:${end}`)
-
if (arr[mid] === val) {
-
return arr[mid]
-
} else if (arr[mid] < val) {
-
start = mid
-
} else if (arr[mid] > val) {
-
end = mid
-
} else {
-
return -1
-
}
-
}
-
}
-
-
let res = findValueUseTwoSplit(102,arr)
-
console.log('最终结果:'+res)
执行结果如图
文章来源: fizzz.blog.csdn.net,作者:拿我格子衫来,版权归原作者所有,如需转载,请联系作者。
原文链接:fizzz.blog.csdn.net/article/details/100014277
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)