使用JS 实现二分法查找位置

举报
拿我格子衫来 发表于 2022/03/17 23:44:33 2022/03/17
【摘要】 使用二分法查找数值的位置: 前提是数组必须是有序的数组, 基本原理是:获取数组的中间值,与要查到的值x进行对比,中间值大于x,则继续对比中间值前半部分数组,依次类推   代码如下: // 生成一个有序数组let createArr = () => { let arr = [] for(let i = 0; i ...

使用二分法查找数值的位置:

前提是数组必须是有序的数组,

基本原理是:获取数组的中间值,与要查到的值x进行对比,中间值大于x,则继续对比中间值前半部分数组,依次类推

 

代码如下:


  
  1. // 生成一个有序数组
  2. let createArr = () => {
  3. let arr = []
  4. for(let i = 0; i < 1000; i++){
  5. arr.push(i)
  6. }
  7. return arr
  8. }
  9. let arr = createArr()
  10. // 使用二分法查找一个值在有序数组中的索引位置
  11. let findValueUseTwoSplit = (val, arr) => {
  12. let start = 0
  13. let end = arr.length - 1 // 获取最大索引
  14. while (start <= end) {
  15. debugger
  16. let mid = Math.ceil((end+start) / 2) // 向上取整
  17. console.log(`start:${start},mid:${mid},end:${end}`)
  18. if (arr[mid] === val) {
  19. return arr[mid]
  20. } else if (arr[mid] < val) {
  21. start = mid
  22. } else if (arr[mid] > val) {
  23. end = mid
  24. } else {
  25. return -1
  26. }
  27. }
  28. }
  29. let res = findValueUseTwoSplit(102,arr)
  30. console.log('最终结果:'+res)

 

 

执行结果如图

文章来源: fizzz.blog.csdn.net,作者:拿我格子衫来,版权归原作者所有,如需转载,请联系作者。

原文链接:fizzz.blog.csdn.net/article/details/100014277

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200