和風(fēng)細(xì)雨

世上本無(wú)難事，心以為難，斯乃真難。茍不存一難之見于心，則運(yùn)用之術(shù)自出。

導(dǎo)航

<

2008年3月

>

日

一

二

三

四

五

六

24

25

26

27

28

29

1

2

3

4

5

6

7

9

11

13

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

統(tǒng)計(jì)

隨筆 - 99
文章 - 1
評(píng)論 - 89
引用 - 0

常用鏈接

留言簿(9)

隨筆分類

隨筆檔案

文章檔案

2007年2月 (1)

相冊(cè)

11

搜索

閱讀排行榜

評(píng)論排行榜

二分查找示例二（對(duì)鏈表進(jìn)行查找）

成員類：

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;

}

/**

* 實(shí)現(xiàn)成員比較

*/

public int compareTo(Object obj){

Member another=(Member)obj;

return this.name.compareTo(another.name);

}

/**

* 實(shí)現(xiàn)成員相等運(yù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;

/**

* 二分查找示例二（對(duì)鏈表進(jìn)行查找）

* @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));

// 測(cè)試鏈表

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+"的下標(biāo)為"+binSearch(members,member));

}

/**

* 二分查找

* @param sortedArray 已排序的欲查找的鏈表

* @param seachValue 查找的值

* @return 找到的元素下標(biāo)，若找不到則返回-1

*/

public static int binSearch(List<Member> sortedList,Member seachValue){

// 左邊界

int leftBound=0;

// 右邊界

int rightBound=sortedList.size()-1;

// 當(dāng)前下標(biāo)位置

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){

// 當(dāng)當(dāng)前下標(biāo)對(duì)應(yīng)的值小于查找的值時(shí)，縮短左邊界

leftBound=curr+1;

}

else{

// 當(dāng)當(dāng)前下標(biāo)對(duì)應(yīng)的值大于查找的值時(shí)，縮短右邊界

rightBound=curr-1;

}

代碼下載：
http://www.aygfsteel.com/Files/junglesong/BinSearch20080308150836.rar

posted on 2008-03-08 15:00 和風(fēng)細(xì)雨閱讀(3016) 評(píng)論(3) 編輯收藏所屬分類: 算法

評(píng)論

# re: 二分查找示例二（對(duì)鏈表進(jìn)行查找） 2010-06-26 01:21 tnt_vampire

二分查找用在鏈表上不但不能使時(shí)間復(fù)雜度降為O(logN),反而比遍歷的O(N)復(fù)雜度更大，變?yōu)榱薕(NlogN)，這是因?yàn)槊看螌?duì)鏈表取下標(biāo)都相當(dāng)要去遍歷一次鏈表；一般來(lái)說(shuō)二分查找只適用于真正可隨機(jī)訪問(wèn)的容器（如vector）。回復(fù) 更多評(píng)論

# re: 二分查找示例二（對(duì)鏈表進(jìn)行查找） 2010-06-26 02:14 tnt_vampire

Sorry，把java接口當(dāng)c++容器看待了，ArrayList確實(shí)是支持隨機(jī)訪問(wèn)的類，不過(guò)博主你這里把List說(shuō)成鏈表很容易讓人誤會(huì)，只能說(shuō)List是支持下標(biāo)索引的接口，具體實(shí)現(xiàn)可不一定支持隨機(jī)訪問(wèn)的哦。回復(fù) 更多評(píng)論

# re: 二分查找示例二（對(duì)鏈表進(jìn)行查找） 2011-03-07 16:44 kevintse

java中ArrayList不是鏈表, LinkedList才是鏈表, 而且鏈表是不支持二分查找的. 回復(fù) 更多評(píng)論

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問(wèn) 管理
相關(guān)文章: 全排列算法示例考試分?jǐn)?shù)排序的三種排序方式的比較二分查找示例二（對(duì)鏈表進(jìn)行查找）二分法查找示例求集合差的幾種算法使用LinkedHashMap進(jìn)行分?jǐn)?shù)排序用匿名類處理分類匯總的方法