<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;
    
    }
    
    
    
        /**
    
     * 實現成員比較
    
         */
    
        public int compareTo(Object obj){
    
        Member another    =(Member)obj;
    
            return this.name.compareTo(another.name);
    
    }
    
    
    
        /**
    
     * 實現成員相等運算
    
         */
    
        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){
    
                    // 左邊界大于右邊界，已經找不到值
    
                    return -1;
    
            }
    
                else{
    
                    if(sortedList.get(curr).compareTo(seachValue)<0){
    
                        // 當當前下標對應的值小于查找的值時，縮短左邊界
    
                        leftBound=curr+1;
    
                }
    
                    else{
    
                        // 當當前下標對應的值大于查找的值時，縮短右邊界
    
                        rightBound=curr-1;
    
                }
    
            }
    
        }
    
    }
    
}
    

    
代碼下載：
    
http://m.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)復雜度更大，變為了O(NlogN)，這是因為每次對鏈表取下標都相當要去遍歷一次鏈表；一般來說二分查找只適用于真正可隨機訪問的容器（如vector）。  回復  更多評論
				  
			
    
		
			
    
				# re: 二分查找示例二（對鏈表進行查找）
					
						2010-06-26 02:14
					
				tnt_vampire
			
    
			
    
				Sorry，把java接口當c++容器看待了，ArrayList確實是支持隨機訪問的類，不過博主你這里把List說成鏈表很容易讓人誤會，只能說List是支持下標索引的接口，具體實現可不一定支持隨機訪問的哦。  回復  更多評論
				  
			
    
		
			
    
				# re: 二分查找示例二（對鏈表進行查找）
					
						2011-03-07 16:44
					
				kevintse
			
    
			
    
				java中ArrayList不是鏈表, LinkedList才是鏈表, 而且鏈表是不支持二分查找的.  回復  更多評論
				  
			
    
		

    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
亚洲国产成人久久一区二区三区|
亚洲欧洲日产专区|
亚洲色欲www综合网|
视频一区二区三区免费观看|
69式互添免费视频|
亚洲啪啪AV无码片|
国产在亚洲线视频观看|
午夜影视在线免费观看|
亚洲第一成年男人的天堂|
一级人做人爰a全过程免费视频|
一区二区无码免费视频网站|
婷婷亚洲综合五月天小说|
国内自产少妇自拍区免费|
亚洲人成电影青青在线播放|
99re这里有免费视频精品|
国产精品亚洲一区二区三区在线
|
国产AV无码专区亚洲AV漫画|
男性gay黄免费网站|
337p日本欧洲亚洲大胆精品555588|
日本一道本高清免费|
亚洲AV永久无码天堂影院
|
四虎永久免费地址在线观看|
国产精品亚洲专区一区|
亚洲国产女人aaa毛片在线|
99久久99久久免费精品小说|
免费国产黄网站在线看|
国产亚洲精品成人a v小说|
中国好声音第二季免费播放|
中文字幕不卡亚洲
|
亚洲一级黄色大片|
成年女人视频网站免费m|
在线看亚洲十八禁网站|
亚洲剧场午夜在线观看|
国产亚洲精品观看91在线|
国产精品高清全国免费观看|
深夜特黄a级毛片免费播放|
亚洲13又紧又嫩又水多|
亚洲丝袜美腿视频|
久久精品国产亚洲AV麻豆王友容|
三年片在线观看免费观看大全动漫|
亚洲色偷偷偷网站色偷一区|