和风细雨

世上本无难事,心以为难,斯乃真难。苟不存一难之见于心,则运用之术自出。

二分查找示例二(对链表进行查找)

成员类:
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.blogjava.net/Files/junglesong/BinSearch20080308150836.rar

posted on 2008-03-08 15:00 和风细雨 阅读(2990) 评论(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才是链表, 而且链表是不支持二分查找的.  回复  更多评论   


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


网站导航: