和风细雨

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

二分查找示例二（对链表进行查找）

成员类：
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 和风细雨 阅读(3005) 评论(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才是链表, 而且链表是不支持二分查找的.  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: