美文网首页html5和js
如何在大量数组中快速找到目标值的下标

如何在大量数组中快速找到目标值的下标

作者: 我的天空是晴天 | 来源:发表于2020-03-11 18:10 被阅读0次

    在js中我们常常会遇到这样的问题,在一个数组中找到目标值的位置。当这个数组很小的时候很简单,直接for循环遍历,把目标值和遍历值对比,如果相等,就返回此时遍历的下标 i。
    但是数组如果很大,这样的方法查询效率会很慢,有木有更好方法呢?    当然有,在下提供一个方法, 二分搜索法。也称折半搜索,是一种在有序数组中查找特定元素的搜索算法。

    实现思路:

      1. 首先从数组中间开始查找对比,若相等则找到,直接返回中间元素的索引。

      2. 若查找值小于中间值,则在小于中间值的那一部分执行步骤1的操作。

      3. 若查找值大于中间值,则在大于中间值的那一部分执行步骤1的操作。

      4. 否则,返回结果为查不到,返回-1。

           function binary_search1(arr, val) {

            var low = 0;

            var high = arr.length - 1;

            while(low <= high) {

                var mid = parseInt((low + high) / 2);

                if(val === arr[mid]) {

                    return mid;

                }

                else if(val < arr[mid]) {

                    high = mid + 1;

                }

                else if(val > arr[mid]) {

                    low = mid - 1;

                }

                else {

                    return-1;           

                 }       

            }     

     }

    var arr = [1,2,3,4,5,6,7,8,9,10,11,12];

    console.log(binary_search1(arr, 3));

    相关文章

      网友评论

        本文标题:如何在大量数组中快速找到目标值的下标

        本文链接:https://www.haomeiwen.com/subject/yucvjftx.html