<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://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)復雜度更大，變為了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才是鏈表, 而且鏈表是不支持二分查找的.  回復  更多評論
				  
			
    
		

    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
成人国产mv免费视频|
一个人看www在线高清免费看|
亚洲欧洲精品成人久久曰影片|
成人性生交大片免费看无遮挡|
亚洲午夜精品一区二区公牛电影院|
久久99精品国产免费观看|
亚洲一区二区三区在线观看精品中文
|
三级网站在线免费观看|
18禁无遮挡无码网站免费|
国产午夜亚洲精品国产|
卡1卡2卡3卡4卡5免费视频|
久久久久亚洲精品无码网址色欲|
在线免费观看韩国a视频|
疯狂做受xxxx高潮视频免费|
av无码东京热亚洲男人的天堂|
一级毛片a免费播放王色电影
|
久久激情亚洲精品无码?V|
中国人免费观看高清在线观看二区|
亚洲人成无码网站|
84pao强力永久免费高清|
亚洲人成人网毛片在线播放|
免费无遮挡无码永久在线观看视频|
日亚毛片免费乱码不卡一区|
亚洲乱色熟女一区二区三区丝袜
|
久久精品国产亚洲7777|
无码囯产精品一区二区免费
|
亚洲国产亚洲综合在线尤物|
日韩午夜免费视频|
中文字幕乱码免费看电影|
亚洲国产成人资源在线软件|
免费A级毛片无码久久版|
久操视频在线免费观看|
中文字幕无码亚洲欧洲日韩|
久久久久亚洲精品无码网址|
曰批全过程免费视频播放网站
|
久久精品视频免费播放|
亚洲人片在线观看天堂无码|
国产综合精品久久亚洲|
巨胸喷奶水视频www网免费|
国产99精品一区二区三区免费|
亚洲国产精品综合久久久|