Javascript的二分查找（预排序数组的查找）

《JavaScript高级程序设计》的作者Nicholas C. Zakas使用JavaScript实现的一些基本算法，链接地址如下http://www.nczonline.net/blog/tag/computer-science/。 其中，对本文提到的二分查找算法的实现如下：

  1. //Copyright 2009 Nicholas C. Zakas. All rights reserved.
  2. //MIT-Licensed, see source file
  3. function binarySearch(items, value){
  4.  
  5.     var startIndex  = 0,
  6.         stopIndex   = items.length – 1,
  7.         middle      = Math.floor((stopIndex + startIndex)/2);
  8.  
  9.     while(items[middle] != value && startIndex < stopIndex){
  10.  
  11.         //adjust search area（调整查找范围）
  12.         if (value < items[middle]){
  13.             stopIndex = middle – 1;
  14.         } else if (value > items[middle]){
  15.             startIndex = middle + 1;
  16.         }
  17.  
  18.         //recalculate middle（重新计算中项索引）
  19.         middle = Math.floor((stopIndex + startIndex)/2);
  20.     }
  21.  
  22.     //make sure it's the right value（确保返回正确的值）
  23.     return (items[middle] != value) ? -1 : middle;
  24. }
Share
Posted in javascript by waiwai at April 24th, 2010.

One Response to “Javascript的二分查找（预排序数组的查找）”

  1. Agatha Hodkinson says:
    December 30, 2010 at 4:23 pm

    Hey, i think you visited my website so here i am!.I am looking for ways to add things to my website!I suppose its ok to use some of your ideas!!

    [Reply]

Leave a Reply