数组二叉查找算法

从数组中查找某一元素的最简单办法就是遍历数组中所有元素,然后和查找值比较,这种查找方式称作线性查找,它适用于未排序的小型数组。对于已排序的大型数组,可以使用二叉查找算法。

该算法首先找到数组中间位置的元素,并将其与查找值比较,如果相等,就返回该元素的索引;否则就将问题简化为查找数组的一半元素。如果查找值小于中间元素,就查找数组的前半部分,否则就查找数组的后半部分。看下面代码:

package {
  import flash.display.Sprite;
  /**
   * @author Flying
   */
  public class Array2 extends Sprite {
    public function Array2() {
      var array : Array = [4, 5, 6, 7, 9, 13, 17];
      trace("13的索引位置: " + indexOf(array, 13));
    }
    /** 采用二叉查找算法 */
    public static function indexOf(array : Array, value : int) : int {
      var low : int = 0;
      var high : int = array.length;
      var middle : int;
      while (low < high) {
        middle = (low + high) / 2; //计算中间元素的索引 
        print(array, middle); //打印数组,用于跟踪查找过程 
        if (array[middle] == value)
          return middle;
        if (value < array[middle])
          high = middle;
        else
          low = middle;
      }
      return -1; //没有找到该元素,返回-1 
    }
    private static function print(array : Array, middle : int) : void {
      for (var i : uint = 0;i < array.length; i++) {
        trace(array[i]);
        if (i == middle)
          trace("*");
        trace("  ");
      }
    }
  }
}
/* 
 4  5  6  7*  9  13  17   
 4  5  6  7  9*  13  17   
 4  5  6  7  9  13*  17   
 13的索引位置:5 
 */

为方便测试,继承了Sprite类。

发表评论