<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://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)復雜度更大，變?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成人片|
国内精品久久久久影院亚洲|
国产精品69白浆在线观看免费|
亚洲人成国产精品无码|
a毛片成人免费全部播放|
91麻豆精品国产自产在线观看亚洲
|
日韩激情无码免费毛片|
亚洲Av永久无码精品黑人|
日本不卡在线观看免费v|
免费人成动漫在线播放r18
|
大地资源在线资源免费观看
|
亚洲午夜成激人情在线影院|
在线看片韩国免费人成视频|
亚洲国产乱码最新视频|
国产成人涩涩涩视频在线观看免费
|
精品亚洲国产成AV人片传媒|
久久久久国色AV免费观看性色
|
免费不卡在线观看AV|
亚洲免费在线视频播放|
曰皮全部过程视频免费国产30分钟
|
黑人大战亚洲人精品一区
|
亚洲网站免费观看|
成年人免费视频观看|
免费无码一区二区|
亚洲AV无码久久|
国产日韩精品无码区免费专区国产
|
免费永久国产在线视频|
国产一级a毛一级a看免费视频
|
亚洲成AV人片在线观看|
99精品国产免费久久久久久下载
|
激情无码亚洲一区二区三区|
18禁男女爽爽爽午夜网站免费|
亚洲一区无码精品色|
无码成A毛片免费|
久久综合亚洲色hezyo|
亚洲国产精品一区二区第一页
|
无码专区永久免费AV网站
|