在Javascript中的二分查找

Question

在Javascript中的二分查找

76

我正在尝试在JavaScript中实现二分查找算法。似乎没什么问题，但我的返回语句似乎返回undefined。有人能告诉我这里出了什么问题吗？

var a = [
    1,
    2,
    4,
    6,
    1,
    100,
    0,
    10000,
    3
];

a.sort(function (a, b) {
    return a - b;
});

console.log('a,', a);

function binarySearch(arr, i) {
    var mid = Math.floor(arr.length / 2);
    console.log(arr[mid], i);
    
    if (arr[mid] === i) {
        console.log('match', arr[mid], i);
        return arr[mid];
    } else if (arr[mid] < i && arr.length > 1) {
        console.log('mid lower', arr[mid], i);
        binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
    } else if (arr[mid] > i && arr.length > 1) {
        console.log('mid higher', arr[mid], i);
        binarySearch(arr.splice(0, mid), i);
    } else {
        console.log('not here', i);
        return -1;
    }
    
}
var result = binarySearch(a, 100);
console.log(result);

- 4m1r

1

另外，为什么arr.splice会修改'a'的值？ - 4m1r

3

要返回递归状态，你需要在每个情况下使用return binarySearch（...）。 - cmbuckley

Splice修改原始数组，参见W3Schools；这包括它通过引用传递。一个好的起点是http://www.nczonline.net/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1/。 - Sunny Patel

它被标记为不太可能对未来的访问者有帮助，因为它只是一个小错误。 - cmbuckley

2

为什么要返回与目标匹配的值？这使整个搜索变得多余！你应该返回索引。 - gb96

28个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jannic Beck · Answer 1

function binarySearch(a = [], x) {
    let length = a.length;
    if (length === 0) {
        return false;
    } else {
        let m = Math.floor(length/2);
        let y = a[m];
        if (x === y) {
            return true;
        } else if (x < y) {
            return binarySearch(a.slice(0, m), x);
        } else {
            return binarySearch(a.slice(m + 1), x);
        }
    }
}

- sg28 · Answer 2

假设数组已排序（可以编写自己的排序算法或者使用内置方法）

function bSearch(array,item){
  var start = 0,
  end = item.length - 1;
  var middle = Math.floor((end+start)/2);
  while(array[middle] !== item && start < end){
    if(item < array[middle]){
      end = middle-1;
     }
    else if(item > array[middle]){
      start = middle+1;
     }
     middle = Math.floor((end+start)/2);

  } 
  if(array[item]!== middle){
     console.log('notFoundMate);
     return -1;
  }
  else {
     console.log('FoundMate);
     return middle;
  }
}

- Nikolay Makhonin · Answer 3

完整功能的二分查找：

负值表示插入点
允许搜索第一个和最后一个索引
起始索引，排除结束索引
自定义比较函数

（此代码和单元测试在此处）

function defaultCompare(o1, o2) {
    if (o1 < o2) {
        return -1;
    }
    if (o1 > o2) {
        return 1;
    }
    return 0;
}

/**
 * @param array sorted array with compare func
 * @param item search item
 * @param start (optional) start index
 * @param end (optional) exclusive end index
 * @param compare (optional) custom compare func
 * @param bound (optional) (-1) first index; (1) last index; (0) doesn't matter
 */
function binarySearch(array, item, start, end, compare, bound) {
    if (!compare) {
        compare = defaultCompare;
    }
    let from = start == null ? 0 : start;
    let to = (end == null ? array.length : end) - 1;
    let found = -1;
    while (from <= to) {
        const middle = (from + to) >>> 1;
        const compareResult = compare(array[middle], item);
        if (compareResult < 0) {
            from = middle + 1;
        }
        else if (compareResult > 0) {
            to = middle - 1;
        }
        else if (!bound) {
            return middle;
        }
        else if (bound < 0) {
            // First occurrence:
            found = middle;
            to = middle - 1;
        }
        else {
            // Last occurrence:
            found = middle;
            from = middle + 1;
        }
    }
    return found >= 0 ? found : -from - 1;
}

- adkelley · Answer 4

你还应该检查“值未找到”的情况，并将其作为第一个基本条件，紧随其后的是成功的搜索。因此，在递归数组时，您不需要检查数组长度>1。最后，由于您不返回数组，为什么不使用Array.prototype.slice方法？

var binarySearch = function(arr, val) {
  var half = Math.floor(arr.length / 2);

  if (arr.length === 0) {
    return -1;
  }
  else if (arr[half] === val) {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return val;
  }
  else if (val > arr[half]) {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return binarySearch(arr.slice(half, arr.length), val);
  }
  else {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return binarySearch(arr.slice(0, half), val);
  }
}


var arr = [1, 5, 20, 58, 76, 8, 19, 41].sort(function(a, b) { return a - b });

console.log("Sorted array: " + arr);
console.log(binarySearch(arr, 76));
console.log(binarySearch(arr, 19));
console.log(binarySearch(arr, 0));

- Jeremy Noel · Answer 5

下午好，我知道这篇文章已经开始了一段时间，但是我认为我可能可以为讨论做出贡献。

function binarySearch(array, target, max, min) {

    //Find the Midpoint between forced max and minimum domain of the array
    var mid = ((max - min) >> 1) + min;
    //alert("Midpoint Number" + mid);
    console.log(mid);
    console.log(array[mid], "target: " + target);

    if (array[mid] === target) {
        //Target Value found
        console.log('match', array[mid], target);
        //alert('match', array[mid], target);
        return mid;
    } 
    else if (mid === 0)
    {
        //All Value have been checked, and none are the target value, return sentinel value
        return -1;
    }
    else if (array[mid] > target)
    {
        //Value at Midpoint is greater than target Value, set new maximum to current midpoint
        max = mid;
        console.log('mid lower', array[mid], target);
        //alert('mid lower', array[mid], target);
        //Call binarySearch with new search domain
        return binarySearch(array, target, max, min);
    } 

    else if (array[mid] < target)
    {
        // Value at Midpoint is less than the target Value, set new minimum to current midpoint
        min = mid;
        console.log('mid higher', array[mid], target);
        //alert('mid higher', array[mid], target);

        //Call binarySearch with new search domain
        return binarySearch(array, target, max, min);
    }

我相信这里还有改进的空间，但是这种方法可以避免对数组进行深度复制（当处理大型数据集时，这可能是一项昂贵的操作），同时它不会以任何方式修改数组。

希望这能帮到你！谢谢， Jeremy

- Rakesh Chaudhari · Answer 6

我认为在JS中实现二分搜索的下面选项很简单。

arr = [1,2,3,4,5];
searchTerm=2;
function binarySearchInJS(start,end)
{
    isFound=false;
    if(end > start)
    {
        //console.log(start+"\t"+end)
        mid =  (end+start)/2;

        mid = Math.floor(mid)

        if(searchTerm==arr[mid])
        {                   
              isFound = true;             
        }
        else
        {   

            if(searchTerm < arr[mid])
            {               
                binarySearchInJS(start,mid);
            }
            if(searchTerm > arr[mid])
            {           
                binarySearchInJS(mid+1,end);
            }
        }
    }

    if(isFound)
    {
        return "Success";   
    }
    else{
            return "Not Found"; 
    }       
}

- Avadhut Thorat · Answer 7

我们开始吧。

let a = [1, 2, 4, 6, 1, 100, 0, 10000, 3];

a.sort(function (a, b) {
    return a - b;
});

function binarySearch(arr,value){
        if(arr.length === 0) return -1;
        var low  = 0 , high = arr.length -1 ,mid ;      
        while (low <= high){
            mid = Math.floor((low+high)/2);     
            if(arr[mid]==value) return mid ; 
            else if (arr[mid]<value) low = mid+1;
            else high = mid-1;          
        }
        return -1 ;
}
console.log(binarySearch(a,1005))

这里是可工作的 fiddle - https://jsfiddle.net/avadhutthorat/6Lq1r582/

- ikrabbe · Answer 8

-2

我想把我的 searchArray 二分查找函数，加上工具函数 insertSortedArray 和 removeSortedArray 加入到答案列表中。我认为这样做很干净，能够全局使用，并且速度优化得相当不错。

- ikrabbe

1

那么把它添加进去呢？我相信问题的答案应该在SO上的答案中包含，不是吗？ - Julix

这是一个Github Gist，我不仅在Stackoverflow上使用它，而且作为一般解决方案。请查找代码并决定如何处理它。 - ikrabbe

那么您的意思是它很可能会改变，因此链接是更好的解决方案，因为读者将看到最新版本？ - Julix

很可能不会改变，因为那个算法非常基本标准，我想我以一种相当简洁、易懂和快速的方式实现了它。这只是我在 JavaScript 中错过的一个漏洞的参考点。 - ikrabbe