logo标签列表

在Javascript中的二分查找

javascriptbinary-search
76

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

Fiddle: http://jsfiddle.net/2mBdL/

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);
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个回答
1
这里有很多过于复杂的答案！如果找到了值，你想返回索引；否则，返回值应该在数组中的负索引。此外，你还希望它足够通用，可以处理语言表达式和数字：
function BinarySearch(array, value) {
    let high = array.length - 1;
    let low = 0;

    if (value < array[low]) 
        return -1;
    if (value > array[high]) 
        return -(high + 1);

    while (high >= low) {
        var mid = (high + low) >> 1;

        if (value === array[mid])
            return mid;
        else if (value < array[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }

    return -(mid + 1);
}

var c = ['alpha','apple','beta','delta','gamma','zebra'];
console.log(BinarySearch(c,'delta')); // return 3
console.log(BinarySearch(c,'beet')); // return -2
var a = [1,2,3,4,6,7,8,9,10];
var b = [1,2,3,4,5,6,7,8,9,10];
console.log(BinarySearch(a,5)); // return -4
console.log(BinarySearch(a,11)); // return -9
console.log(BinarySearch(b,5)); // return 4
console.log(BinarySearch(b,0)); // return -1

或者，如果您只想在找到时返回true，否则返回false：

function BinarySearch(array, value) {
    let high = array.length - 1;
    let low = 0;

    if (value < array[low] || value > array[high]) 
        return false;

    while (high >= low) {
        let mid = (high + low) >> 1;

        if (value === array[mid])
            return true;
        else if (value < array[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }

    return false;
}
1
你的代码对我来说是最易读的，所以我投了票。但是我不能轻松地阅读-++，在我看来，用~替换它可以翻转所有位，并且等于-++： n = -1 * (p + 1) = ~p - BitLauncher
谢谢！可读性是编写代码的关键。你对“-++”部分提出了一个公正的观点。我对它并不太满意，但选择了它而不是其他选项。我采纳了你的建议并进行了修改。 - WesleyAC
1

一种递归的二分查找函数，将返回正在搜索的元素的 索引：

function binarySearch(arr, target, idx=0){
  let full_len = arr.length;
  if(full_len === 0){
    return null;
  }
  let mid = Math.floor(full_len / 2);
  if(arr[mid] === target){
    return `INDEX of ${target} is: ${idx+mid}`;
  }else if(target > arr[mid]){
    let right = arr.slice(mid + 1, full_len);
    idx += (full_len - right.length);
    return binarySearch(right, target, idx);
  }else if(target < arr[mid]){
    let left = arr.slice(0, mid);
    return binarySearch(left, target, idx);
  }
}

//Testing:

var arr = [1, 27, 34, 42, 58, 69, 71, 85, 96, 151];
console.log(binarySearch(arr, 1)); //=> 0
console.log(binarySearch(arr, 27)); //=> 1
console.log(binarySearch(arr, 34)); //=> 2
console.log(binarySearch(arr, 42)); //=> 3
console.log(binarySearch(arr, 58)); //=> 4
console.log(binarySearch(arr, 69)); //=> 5
console.log(binarySearch(arr, 71)); //=> 6
console.log(binarySearch(arr, 85)); //=> 7
console.log(binarySearch(arr, 96)); //=> 8
console.log(binarySearch(arr, 151)); //=> 9
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
console.log(binarySearch(arr, 10)); //=> 0
console.log(binarySearch(arr, 20)); //=> 1
console.log(binarySearch(arr, 30)); //=> 2
console.log(binarySearch(arr, 40)); //=> 3
console.log(binarySearch(arr, 50)); //=> 4
console.log(binarySearch(arr, 60)); //=> 5
console.log(binarySearch(arr, 70)); //=> 6
console.log(binarySearch(arr, 80)); //=> 7
console.log(binarySearch(arr, 90)); //=> 8
console.log(binarySearch(arr, 100)); //=> 9

var bigArr = [];
for(var i = 1; i <= 1000000; i++){
  bigArr.push(i);
}
console.log(binarySearch(bigArr, 5342)) //=> 5341
console.log(binarySearch(bigArr, 254369)) //=> 254368
console.log(binarySearch(bigArr, 2000000)) //=> null
console.log(binarySearch(bigArr, -1)) //=> null
0

const SearchArray =(Listarr, Key)=>{
  
  const midvalues = Math.floor(Listarr.length/2)
 
  if(Key===Listarr[midvalues]) return true
  
  else if(Listarr[midvalues]<=Key && midvalues>0 )
    return SearchArray(Listarr.slice(midvalues,Listarr.length), Key)
  
  else if(Listarr[midvalues]>=Key && midvalues>0 )
    return SearchArray(Listarr.slice(0, midvalues) , Key)
  else
    return "No record found"
  
  
}
const arr = [11,24,26,37,40,43,56,75,87];

console.log(SearchArray(arr, 75))
console.log(SearchArray(arr, 87))
console.log(SearchArray(arr, 11))
console.log(SearchArray(arr, 26))

0
这里是一个使用默认比较函数的 ES6 函数，采用函数式编程风格，如果没有提供，则假定数字比较，否则为字符串比较。 

function binarySearch(arr, val, compFunc = 
    (a, b) => typeof val == 'number' ? a-b : a.localeCompare(b), i=0, j=arr.length) {
  return i >= j ? i
    : ( mid =>
          ( cmp => 
              cmp < 0 ? binarySearch(arr, val, compFunc, i, mid) 
            : cmp > 0 ? binarySearch(arr, val, compFunc, mid+1, j) 
            : mid 
          ) (compFunc(val, arr[mid]))
      ) (i + j >> 1);
}

///////// Tests ///////////////////

function check(arr, val, compFunc) {
  var fmt = JSON.stringify;
  var result = binarySearch(arr, val); // default compFunc is assumed
  console.log(`binarySearch(${fmt(arr)}, ${fmt(val)}) == ${fmt(result)}`);
  if (result > arr.length || result < 0 || !arr.length && result 
    || result < arr.length && compFunc(val, arr[result]) > 0
    || result > 0 && compFunc(val, arr[result-1]) < 0) throw "Unexpected result!!!"
}

// Tests with numeric data:
for (var val = 0; val < 12; val++)      
  check([1, 2, 4, 6, 9, 9, 10], val, (a,b) => a-b);
// Test with empty array:
check([], 12, (a,b) => a-b);
// Test with string data:
check(['abc', 'deaf', 'def', 'g'], 'dead', (a, b) => a.localeCompare(b));

最好简化代码，以便初学者能够理解。 - Kiran Mohan
我想提供一个基于ES6功能的版本。你不明白它的哪个部分？ - trincot
2
具有讽刺意味。这可能是最优雅的解决方案，但过于繁琐的函数调用开销和过度分支使其相当缓慢，并且以远为内存效率最低，因为它必须通过每个内层时都会创建大量新变量。 - Jack G
0

zig的binarySearch移植版：

  • 使用<代替<=，少一次比较
  • 以上可用于right的无符号int - 适用于像zig或rust这样的语言
  • 计算中间位置时避免了溢出mid - 适用于像zig或rust这样的语言
const binarySearch = (key, items, compareFn) => {
  let left = 0;
  let right = items.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const cmp = compareFn(key, items[mid]);
    if (cmp === 0) return mid;
    if (cmp < 0) right = mid;
    else left = mid + 1;

    // happens when right = items.length - 1 and key = 2 and items = [3]
    if (right < 0) throw new Error("right is < 0");
  }
  return -1;
};

const compareFn = (a, b) => a - b;
console.log(binarySearch(33, new Int16Array([1, 3, 4, 2, 33, 20, 10, 12, 34]).sort(), compareFn));
console.log(binarySearch(2, new Int16Array([3]).sort(), compareFn));
0

无变异和递归

let A = [ ...Array(100).keys() ].map((x) => Math.floor(Math.random() * 1000)).sort((a,b) => a-b)
const binarySearch = (A, a, b, k) => {
  const m = Math.floor((b + a)/ 2);
  console.log(a, m, b, k)
  if(A[m] === k) { 
    return m; 
  }

  if(A[a] <= k && k <= A[m]) { 
    return binarySearch(A, a,   m, k) 
  }

  if(A[m] <  k && k <= A[b]) { 
    return binarySearch(A, m+1, b, k) 
  }

  return -1;
}
console.log(`key ${A[30]}`);
rez = binarySearch(A, 0, 100, A[30])
console.log(`rez is ${rez} and index of ${A[30]} is ${A.indexOf(A[30])}`);

rez = binarySearch(A, 0, 100, 666)
console.log(`rez is ${rez} and index of ${666} is ${A.indexOf(666)}`);

0

递归地将搜索范围一分为二，直到达到适当的值或超出搜索范围：

const binarySearch = (arr, item, [low=0, high=arr.length-1]=[]) => {
  const mid = Math.floor((low + high)/2)

  if (low > high) return -1 // is overshooting the range?
  if (arr[mid] === item) return mid // is item found?

  return binarySearch(arr, item, [
    item > arr[mid] ? mid+1 : low,
    item < arr[mid] ? mid-1 : high
  ])
}

让我们来测试一下：

// positive
console.log(binarySearch([2, 6, 9, 14, 21],  9)) // => 2
console.log(binarySearch([2, 6, 9, 14, 21], 21)) // => 4
console.log(binarySearch([2, 6, 9, 14, 21],  2)) // => 0

// negative
console.log(binarySearch([2, 6, 9, 14, 21],  0)) // => -1
console.log(binarySearch([2, 6, 9, 14, 21], -4)) // => -1
console.log(binarySearch([2, 6, 9, 14, 21], 40)) // => -1
将 if (low > high) return -1 改为 if (low > high) return -low-1，你就得到了一个二分查找，当未找到 item 时可以返回插入点。 :) - vivimice
-1
假设有一个已排序的数组，下面是一个递归二分查找算法：
function binSearch(needle, arr) {
  length = arr.length;
  while(length > 1) {
    midpoint = Math.floor(length/2);
    return (needle > arr[midpoint-1]) ? 
           binSearch(needle, arr.splice(midpoint, length)) :    
           binSearch(needle, arr.splice(0, midpoint));
  }
  return needle === arr[0] ? arr[0] : -1;
}
递归函数调用 = 缓慢的代码; 几乎每天都是这样 (几乎没有例外)。 - Jack G
1
@JackGiffin：更不用说splice了（在这里解释为什么它不好）。尽管如此，我还是因其简单和教学质量而点赞。 - 7vujy0f0hy
@7vujy0f0hy 请帮我。我看不到这段代码的教学质量。在这个代码片段中，splice的使用违反了直觉，因为它被用来剪切掉不需要的部分，而不是聚焦于搜索数组中所需的部分。 - Jack G
@JackGiffin：演示原则，没有技术上的混乱。清晰简洁，易于阅读。最小化可行代码，易于记忆。为了清晰而牺牲效率，让学生有自由改进以适用于实际应用。展示更好的 - 你做不到。 P.S. 你的 splice 参数是“杯子是半空”的级别。 - 7vujy0f0hy
-1

function binarySearch(arr, num, l, r){
 if( arr instanceof Array ){
   
    l = isNaN(l) ? 0 : l;
    r = isNaN(r) ? arr.length - 1: r;
    let mid = l + 1 + Math.round((r - l)/2 - 1);    
    console.log(l, r, mid, arr[mid]);
    
    if( num == arr[mid] ){ 
     console.log("found"); 
      return mid; 
    }
    
    if( typeof arr[mid] == "undefined" || l == r ){
     console.log("not found"); return -1;
    }
    
    if( num < arr[mid] ){  
     console.log("take left"); 
      return binarySearch(arr, num, l, r - mid);
    }
    
    console.log("take right");
    return binarySearch(arr, num, mid, r);
    
  }
}

console.log( binarySearch([0, 0, 1 ,1, 2, 3, 5, 6, 11], 2) );

沉默错误会自掘坟墓（请注意函数仅在if（arr instanceof Array）执行）。当然，一开始看起来很好：文件大小更小。但是，沉默的错误慢慢聚合成一只毒蛇。有一天，这个象征性的蛇突然向你发起攻击，通过使您的程序无法正常工作而将您击倒。但最糟糕的还没有到来：比喻性的毒液渗入您的血管，使您病得厉害，防止您找到代码中问题的源头。在痛苦和绝望中呼出最后一口气，您现在后悔使用所有的沉默错误。 - Jack G
-1

要使用它，只需将其原样复制粘贴，以使用本地变量提高速度。并修改搜索的值，例如如果您在子对象或数组中搜索：

if (array[mid][0] < value[0]) low = mid + 1;
if (array[mid].val < value.val) low = mid + 1;

为了更快的结果，请使用数组或数组的数组或并行数组，将搜索的数组复制到本地变量中。非局部变量或每次执行obj.something都会减慢速度。

这是最快的版本：

let array=[3,4,5,6]
let value=5; //searched value
let mid, low = 0,high = array.length;
while (low < high) {
    mid = low + high >>> 1; // fast divide by 2 and round down
    if (array[mid] < value) low = mid + 1;
    else high = mid;
}
//if (array[mid] != value) mid=-1;// this might not be required if you look for place to insert new value
mid;// contains the found value position or if not found one before where it would be if it was found

二分查找的工作原理如下：

|           .           |     // find middle
//option 1:
|           .     v     |     // if value on right, middle is top
            |     .     |     // so then it is like this
//option 2:                    
|     v     .           |     // if value on left, middle is bottom
|     .     |                 // so then it is like this
//more loops of option 2 until not found
|  .  |                       // next time it will be like this
|. |                          // next time it will be like this
.                             // next time it will be like this

如果未找到，此实现会转到底部。 它始终可以找到或未找到。 它返回小于或等于搜索值的索引。 因此，您需要检查它是否相等。验证该值是否存在或仅低于一个结果。如果您正在寻找要按顺序插入的位置，请将其放在那个位置，无需检查是否相等。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接