二分法搜索List<T>泛型集合

快来打我* 2023-10-17 23:06 49阅读 0赞

List集合在项目开发中是最常用的一个集合，在项目中经常需要从集合中查找某一个对象，如果直接用for循环小数据量时没什么性能问题，但是数据量非常大时，用for循环就会显得特别慢。本文将详细讲解如何利用二分法从List<T>集合中查询泛型对象。

需求：传入一个List<T>集合，从中搜索指定排序属性值对应的对象。

思路：未明确指定集合中的对象，所以我们需要使用泛型；未指明对象排序属性类型，所以我们需要考虑排序属性类型，便于比较；未指明传入的集合是升序排序还是降序排序，所以我们需要将传入的集合排序。

请看一下代码（代码中附讲解）：

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;
    	}
    
    	@Override
    	public 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;
    	}
    
    	@Override
    	public 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;
    	}
    
    	@Override
    	public String toString() {
    		return "UserInfo [id=" + id + ", age=" + age + ", name=" + name + "]";
    	}
    
        //重写compareTo方法实现用于排序，排序属性为用户ID
    	@Override
    	public 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();
    		}
    	}

测试输出结果：

![70][]

以上方法你学会了吗？快动手试试吧。

[70]: https://img-blog.csdn.net/20180805213008104?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQyNjc5MDA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70