二分法搜索List<T>泛型集合
List集合在项目开发中是最常用的一个集合，在项目中经常需要从集合中查找某一个对象，如果直接用for循环小数据量时没什么性能问题，但是数据量非常大时，用for循环就会显得特别慢。本文将详细讲解如何利用二分法从List
需求：传入一个List
思路：未明确指定集合中的对象，所以我们需要使用泛型；未指明对象排序属性类型，所以我们需要考虑排序属性类型，便于比较；未指明传入的集合是升序排序还是降序排序，所以我们需要将传入的集合排序。
请看一下代码（代码中附讲解）：
package test;import java.lang.reflect.Field;import java.util.ArrayList;import java.util.Collections;import java.util.List;//构建一个搜索工具类，指定泛型对象必须实现Comparable接口public class RecursionDichotomy<T extends Comparable<T>> {//比较属性名private String searchKey;//传入的集合private List<T> data = new ArrayList<T>();//构造方法public RecursionDichotomy(List<T> data, String searchId) {this.data = data;this.searchKey = searchId;//排序，升序Collections.sort(this.data);}//排序属性get,set方法public String getSearchKey() throws Exception {if (null == searchKey || "".equals(searchKey)) {throw new Exception("searchKey is null !");}return searchKey;}public void setSearchKey(String searchKey) {this.searchKey = searchKey;}//对外调用接口排序属性为字节型public T search(Byte id) throws Exception {return search(data, id);}//对外调用接口排序属性为短整型public T search(Short id) throws Exception {return search(data, id);}//对外调用接口排序属性为整型public T search(Integer id) throws Exception {return search(data, id);}//对外调用接口排序属性为长整型public T search(Long id) throws Exception {return search(data, id);}//对外调用接口排序属性为单精度浮点型public T search(Float id) throws Exception {return search(data, id);}//对外调用接口排序属性为双精度浮点型public T search(Double id) throws Exception {return search(data, id);}//对外调用接口排序属性为字符串public T search(String id) throws Exception {return search(data, id);}//定义一个内部私有公共方法，通过递归实现二分法查找指定排序属性值得对象private T search(List<T> searchData, Object id) throws Exception {//获取集合中间值int midle = searchData.size() / 2;//获取传入属性值得类型String type = id.getClass().getTypeName();type=type.substring(type.lastIndexOf(".")+1);//获得集合中间对象T mt = searchData.get(midle);//通过反射获取T排序属性对应的值Field field = mt.getClass().getDeclaredField(this.getSearchKey());//设置属性可以被访问（主要防止对象中定义的属性为私有（private）属性）field.setAccessible(true);//比较传入的排序属性值与当前传入集合中间对象的排序属性值，本文这里只考虑基本数据类型（布尔类型除外）和String类型属性。int rin = 2;switch (type) {case "Byte":Byte by = field.getByte(mt);rin = by.compareTo((Byte) id);case "Short":Short sh = field.getShort(mt);rin = sh.compareTo((Short) id);break;case "Integer":Integer in = field.getInt(mt);rin = in.compareTo((Integer) id);break;case "Long":Long lo = field.getLong(mt);rin = lo.compareTo((Long) id);break;case "Float":Float fl = field.getFloat(mt);rin = fl.compareTo((Float) id);break;case "Double":Double dou = field.getDouble(mt);rin = dou.compareTo((Double) id);break;case "String":String st = (String) field.get(mt);rin = st.compareTo((String) id);break;default:rin=2;break;}//传入的属性值小于集合中间对象排序值，取集合左边子集合传入当前方法if (rin == 1) {return this.search(searchData.subList(0, midle), id);//传入的属性值大于集合中间对象排序值，取集合右边子集合传入当前方法} else if (rin == -1) {return this.search(searchData.subList(midle, searchData.size()), id);//传入的属性值等于当前中间值时，返回该对象。} else if (rin == 0) {return mt;}return null;}}
以上代码是对我们最开始需求的实现，下面我们定义一个对象，测试我们写的方法。
定义一个用户对象：
package test;//用户对象，需实现Comparable，因为我们封装的方法指明了集合中的对象需要实现Comparable接口public class UserInfo implements Comparable<UserInfo> {private int id;private int age;private String name;public UserInfo() {super();}public UserInfo(int id, int age, String name) {super();this.id = id;this.age = age;this.name = name;}public int getId() {return id;}public void setId(int id) {this.id = id;}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;}@Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + age;result = prime * result + id;result = prime * result + ((name == null) ? 0 : name.hashCode());return result;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;UserInfo other = (UserInfo) obj;if (age != other.age)return false;if (id != other.id)return false;if (name == null) {if (other.name != null)return false;} else if (!name.equals(other.name))return false;return true;}@Overridepublic String toString() {return "UserInfo [id=" + id + ", age=" + age + ", name=" + name + "]";}//重写compareTo方法实现用于排序，排序属性为用户ID@Overridepublic int compareTo(UserInfo o) {if (this.id > o.getId()) {return 1;} else if (this.id < o.getId()) {return -1;} else {return 0;}}}
用户对象定义好了，下面我们来测试下我们写的方法：
public static void main(String[] args) {List<UserInfo> data = new ArrayList<UserInfo>();UserInfo u1=new UserInfo();u1.setId(1);UserInfo u2=new UserInfo();u2.setId(2);UserInfo u3=new UserInfo();u3.setId(3);UserInfo u4=new UserInfo();u4.setId(4);UserInfo u5=new UserInfo();u5.setId(5);UserInfo u6=new UserInfo();u6.setId(6);UserInfo u7=new UserInfo();u7.setId(7);UserInfo u8=new UserInfo();u8.setId(8);data.add(u8);data.add(u7);data.add(u5);data.add(u6);data.add(u4);data.add(u1);data.add(u2);data.add(u3);RecursionDichotomy<UserInfo> rd = new RecursionDichotomy<UserInfo>(data, "id");UserInfo userInfo = null;try {userInfo = rd.search(7);System.out.println("搜索到的结果：" + userInfo.toString());userInfo = rd.search(4);System.out.println("搜索到的结果：" + userInfo.toString());userInfo = rd.search(1);System.out.println("搜索到的结果：" + userInfo.toString());} catch (Exception e) {e.printStackTrace();}}
测试输出结果：
以上方法你学会了吗？快动手试试吧。
小灰灰
快来打我*
超、凢脫俗
小鱼儿
淩亂°似流年
还没有评论，来说两句吧...