在希腊帕尔纳斯山南坡上,有一个驰名世界的戴尔波伊神托所,在它的入口处的巨石上赫然锈刻着这样几个大字: 认识你自己!

像丁香花一样静静的等待

   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 2 文章 :: 32 评论 :: 0 Trackbacks

   从数组中查找特定数据的最简单办法就是遍历数组中所有的元素,这种查找方式称为线性查找。对于小型数组或者是没有经过排序的数组的可以采用这样的办法,对于已经排序的数组可以采用高效的二叉查找算法。该算法查找数组中位于中间位置的元素,并将其与查找值比较,如果两者相等就返回该元素的索引,否则将问题化简为查找元素的一半来处理。

    class ArrayFinder{

  public static void print(int[] array,int middle){
     for(int i=0;i<array.length;i++){
        System.out.print(array[i]);
        if(i == middle)System.out.print("*");
        System.out.print(" ");
     }
     System.out.println();
  }
 
  public static int indexOf(int[] array,int value){
     int low = 0;
     int high = array.length-1;
     int middle;
     while(low <= high){
        middle = (low + high)/2;
        print(array,middle);
        if(array[middle] == value) return middle;
       
        if(value < array[middle]) //要比较的值比中间值小
           high = middle +1;
        else
           low = middle - 1;
     }
     return -1;
  }
  public static void main(String[] args){
    int[] array = new int[]{1,2,3,4,6,9,12};
    System.out.println("location of 13: "+indexOf(array,4));
  }
 
}

Result :
D:\jcode>javac ArrayFinder.java

D:\jcode>java ArrayFinder
1 2 3 4* 6 9 12
location of 13: 3

posted on 2007-03-02 12:04 dyin 阅读(1437) 评论(4)  编辑  收藏

评论

# re: 数组的二叉查找算法【java description】 2007-06-09 03:14 蚕豆
呵呵 不太理解 真是惭愧  回复  更多评论
  

# re: 数组的二叉查找算法【java description】 2007-09-23 14:41 vvv
把数组的查找算法 总结一下   回复  更多评论
  

# re: 数组的二叉查找算法【java description】 2008-05-19 20:43 何维
如果你这个能执行出正确的结果,那就鬼见愁了。
if(value < array[middle]) //要比较的值比中间值小
high = middle +1;
else
low = middle - 1;
应改为
if(value < array[middle]) //要比较的值比中间值小
high = middle -1;
else
low = middle + 1;
  回复  更多评论
  

# re: 数组的二叉查找算法【java description】[未登录] 2010-08-22 10:50 test
这个是二分  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: