利用二分查找获得List中小于并且最接近的数

- 日理万妓 2023-02-20 02:35 21阅读 0赞

引言

最近在老系统中看到了一大段代码，这个代码的目的是迁移迁移历史，在迁移的过程中需要很多计算，我大概看了一下代码，里面到处都是for 循环，虽然for循环的逻辑比较简单，但是循环的次数太多了， 这就导致这个方法非常的慢，其中有一个地方就是通过循环获得日期。

如果list中有5000个日期，恰好这个要查找的日期在最后面一个，那么肯定完蛋。 如果通过二分查找肯定会会少很多循环。

目标：找到集合中早于目标日期，并且最接近的一个日期，如果没有早于的则不返回

代码：

package com.zqf.platformweb.statistics.service;
    
    import java.text.SimpleDateFormat;
    import java.util.ArrayList;
    import java.util.Date;
    import java.util.List;
    
    /**
     * @author zhenghao
     * @description:
     * @date 2020/6/2118:45
     */
    public class test {
    
        public static void main(String[] args) throws Exception {
            SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
            Integer c = 0;
            //需要一个有序且不重复的数组
            List<Date> number = new ArrayList<>();
            number.add(sdf.parse("2010-04-10"));
            number.add(sdf.parse("2013-03-14"));
            number.add(sdf.parse("2015-07-18"));
            number.add(new Date());
            number.add(sdf.parse("2025-07-16"));
            System.out.println(find(number, 0, number.size()-1, sdf.parse("2025-07-16"), c));
        }
    
        public static Date find(List<Date> number, Integer start, Integer end, Date k, Integer c){
            c++;
            //如果只剩一个 直接返回
            if (start.equals(end)){
                Date startN = number.get(start);
                if (!startN.after(k)){
                    return startN;
                }
                return null;
            }
            //如果只剩两个  返回最小的那个
            if (Math.abs(start-end) == 1){
                Date startN = number.get(start);
                Date endN = number.get(end);
                if (!endN.after(k)){
                    return endN;
                }
                if (!startN.after(k)){
                    return startN;
                }
                return null;
    
            }
            int midle = (start + end)/2;
            Date right = number.get(midle+1);
    
            //如果左边差值 比 右边差值 小 递归左半部分
            if (!right.after(k)){
                return find(number, midle + 1, end, k, c);
            }else {
                return find(number, start, midle , k, c);
            }
        }
    
    }

经过测试，效果有很多提升，各位读者可以根据自己的需求，采用合适的算法来提升性能。

总结

如果能深入的了解数据结构和算法，在代码性能优化方面会有更多的思路，效果也会有明显提升。