<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        


    


    和風細雨
    

    世上本無難事，心以為難，斯乃真難。茍不存一難之見于心，則運用之術自出。
    

    




    
	
					
	
    
		
    
			二分查找示例二（對鏈表進行查找）
		
    
		成員類：
    

    package com.junglesong;
    

    
    public class Member implements Comparable{
    
        private String name;
    
        private int age;
    
    
    
        public Member(String name,int age){
    
            this.name=name;
    
            this.age=age;
    
    }
    
    
    
        /**
    
     * 實現(xiàn)成員比較
    
         */
    
        public int compareTo(Object obj){
    
        Member another    =(Member)obj;
    
            return this.name.compareTo(another.name);
    
    }
    
    
    
        /**
    
     * 實現(xiàn)成員相等運算
    
         */
    
        public boolean equals(Object obj){
    
        Member another    =(Member)obj;
    
            return this.name.equals(another.name);
    
    }
    
    
    
        public String toString(){
    
            return "名="+name+" 年齡="+age;
    
    }
    

    
        public int getAge() {
    
            return age;
    
    }
    

    
        public void setAge(int age) {
    
            this.age = age;
    
    }
    

    
        public String getName() {
    
            return name;
    
    }
    

    
        public void setName(String name) {
    
            this.name = name;
    
    }
    
}
    

    

    
二分查找類：
    

    package com.junglesong;
    

    
    import java.util.ArrayList;
    
    import java.util.List;
    

    
    /**
    
 * 二分查找示例二（對鏈表進行查找）
    
 *     @author: sitinspring(junglesong@gmail.com)
    
 * @date: 2008-3-8
    
     */
    
    public class BinSearch2{
    
        public static void main(String[] args){
    
            // 欲查找的鏈表
    
            List<Member> members=new ArrayList<Member>();
    
        members.add(    new Member("Andy",21));
    
        members.add(    new Member("Bill",22));
    
        members.add(    new Member("Cindy",23));
    
        members.add(    new Member("Douglas",24));
    
        members.add(    new Member("Felex",25));
    
        members.add(    new Member("Green",26));
    
        
    
            // 測試鏈表
    
            List<Member> tempList=new ArrayList<Member>();
    
        tempList.add(    new Member("Bill",22));
    
        tempList.add(    new Member("Cindy",23));
    
        tempList.add(    new Member("Douglas",24));
    
        tempList.add(    new Member("Felex",25));
    
        tempList.add(    new Member("Hill",26));
    
        
    
            for(Member member:tempList){
    
            System.out.println(    "成員"+member+"的下標為"+binSearch(members,member));
    
        }
    
    }
    
    
    
        /**
    
     * 二分查找
    
     *     @param sortedArray 已排序的欲查找的鏈表
    
     *     @param seachValue 查找的值
    
     *     @return 找到的元素下標，若找不到則返回-1
    
         */
    
        public static int binSearch(List<Member> sortedList,Member seachValue){
    
            // 左邊界
    
            int leftBound=0;
    
            // 右邊界
    
            int rightBound=sortedList.size()-1;
    
            // 當前下標位置
    
            int curr;
    
        
    
            while(true){
    
                // 定位在左邊界和右邊界中間
    
                curr=(leftBound+rightBound)/2;
    
            
    
                if(sortedList.get(curr).equals(seachValue)){
    
                    // 找到值
    
                    return curr;
    
            }
    
                else if(leftBound>rightBound){
    
                    // 左邊界大于右邊界，已經(jīng)找不到值
    
                    return -1;
    
            }
    
                else{
    
                    if(sortedList.get(curr).compareTo(seachValue)<0){
    
                        // 當當前下標對應的值小于查找的值時，縮短左邊界
    
                        leftBound=curr+1;
    
                }
    
                    else{
    
                        // 當當前下標對應的值大于查找的值時，縮短右邊界
    
                        rightBound=curr-1;
    
                }
    
            }
    
        }
    
    }
    
}
    

    
代碼下載：
    
http://www.tkk7.com/Files/junglesong/BinSearch20080308150836.rar 

		
    
			posted on 2008-03-08 15:00 和風細雨 閱讀(3013) 評論(3)  編輯  收藏  所屬分類: 算法 
		
    
	
    
	
	





    
	    
    


    

    評論
    
	
	
			
    
				# re: 二分查找示例二（對鏈表進行查找）
					
						2010-06-26 01:21
					
				tnt_vampire
			
    
			
    
				二分查找用在鏈表上不但不能使時間復雜度降為O(logN),反而比遍歷的O(N)復雜度更大，變?yōu)榱薕(NlogN)，這是因為每次對鏈表取下標都相當要去遍歷一次鏈表；一般來說二分查找只適用于真正可隨機訪問的容器（如vector）。  回復  更多評論
				  
			
    
		
			
    
				# re: 二分查找示例二（對鏈表進行查找）
					
						2010-06-26 02:14
					
				tnt_vampire
			
    
			
    
				Sorry，把java接口當c++容器看待了，ArrayList確實是支持隨機訪問的類，不過博主你這里把List說成鏈表很容易讓人誤會，只能說List是支持下標索引的接口，具體實現(xiàn)可不一定支持隨機訪問的哦。  回復  更多評論
				  
			
    
		
			
    
				# re: 二分查找示例二（對鏈表進行查找）
					
						2011-03-07 16:44
					
				kevintse
			
    
			
    
				java中ArrayList不是鏈表, LinkedList才是鏈表, 而且鏈表是不支持二分查找的.  回復  更多評論
				  
			
    
		

    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
波多野结衣在线免费视频|
黄视频在线观看免费|
四虎国产成人永久精品免费|
亚洲精品国产高清不卡在线|
国产精品亚洲av色欲三区|
免费黄色网址入口|
亚洲av无码一区二区三区四区|
免费无码看av的网站|
亚洲日本天堂在线|
亚洲av中文无码|
yellow视频免费在线观看|
亚洲香蕉成人AV网站在线观看|
国产精品美女久久久免费|
久久久久久久综合日本亚洲|
久久久免费的精品|
亚洲久悠悠色悠在线播放|
国产免费久久精品久久久|
成人特级毛片69免费观看|
亚洲香蕉网久久综合影视|
亚洲一区免费视频|
亚洲精品乱码久久久久久V|
亚洲日本va午夜中文字幕久久|
在线观看肉片AV网站免费|
中文字幕亚洲精品资源网|
免费av欧美国产在钱|
在线观看国产一区亚洲bd|
亚洲综合色成在线播放|
97视频免费观看2区|
亚洲精品乱码久久久久蜜桃|
亚洲热妇无码AV在线播放|
又粗又大又黑又长的免费视频|
美女视频黄频a免费大全视频|
亚洲国产精品嫩草影院在线观看
|
亚洲成人免费电影|
亚洲一卡2卡3卡4卡5卡6卡|
亚洲阿v天堂在线2017免费|
91高清免费国产自产拍2021|
亚洲免费网站观看视频|
亚洲成色在线综合网站|
成人免费无码视频在线网站|
国产免费一级高清淫曰本片|