如何在Java中的Arraylist中实现二进制搜索过程

Question

我不知道如何在Java的Arraylist中实现二进制搜索过程。

有两个显示机场名称和两个机场名称之间路线的数组列表。

这里是下面定义的airportName和Route Class。

public class AirportName{
    private String airportName;
}

public class Route{
    private String takeOffPoint;
    private String landingPoint;
}

机场名称在Arraylist中定义为机场名称的缩写，例如（JFK）路线名称定义为路线对象，包括Arraylist中的起飞点和着陆点，例如（肯尼迪国际机场-TLV）

由于每个数组列表中的机场名称和路线很多，其大小都超过30000，因此我必须使用二进制搜索来实现代码的优化。

我已经完成了不使用二进制搜索的过程。

如何通过二进制搜索做到这一点？

这是我的代码段，如下所示。

ArrayList<AirportName> airportNames = ShowProcess.getAirports();
ArrayList<Route> routeNamesList = ShowProcess.getAirportRoutes();

机场名称

Scanner sc = new Scanner(System.in);
    System.out.print("Enter AirportName : ");
    String airportName = sc.nextLine(); 

    boolean checkAirportNameValid = false;

    for(AirportName airport : airportNames) {
        if(airport.getAirportName().equals(airportName)) {
            checkAirportNameValid = true;
        }
    }

路由名称

public static ArrayList<String> searchProcess(String airportName, ArrayList<Route> routeNamesList) {
        ArrayList<String> destinationNames = new ArrayList<String>();
        for(Route route : routeNamesList) {
            if(route.getTakeOffPoint().equals(airportName)) {
                destinationNames.add(route.getLandingPoint());
            }
        }

        return destinationNames;
}

Answer 1

这是我的解决方案。可行

public static Integer[] binarySearch(ArrayList<Route> routeNamesList, Comparable key) {
        ArrayList<Integer> arrList = new ArrayList<Integer>();
        int lo = 0, hi = routeNamesList.size() - 1, mid;
        routeNamesList.sort((str1, str2) -> str1.getTakeOffPoint().compareTo(str2.getTakeOffPoint()));

        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(routeNamesList.get(mid).getTakeOffPoint());
            if (cmp == 0) {
                int lowerBoundary = lowerIndex(routeNamesList, key, lo, mid);
                int upperBoundary = upperIndex(routeNamesList, key, mid, hi);
                for(int i = lowerBoundary; i <= upperBoundary; i++) {
                    arrList.add(i);
                }
                break;
            } else if (cmp < 0)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return arrList.stream().toArray(Integer[]::new);
    }

    public static int lowerIndex(ArrayList<Route> routeNamesList, Comparable key, int lo, int hi) {
        int mid;
        int lastMatch = hi;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(routeNamesList.get(mid).getTakeOffPoint());
            if (cmp == 0) {
                lastMatch = mid;
                hi = mid - 1;
            } else if (cmp < 0) {
                lo = mid + 1;
            } else {
                break;
            }
        }

        return lastMatch;
    }

    public static int upperIndex(ArrayList<Route> routeNamesList, Comparable key, int lo, int hi) {
        int mid;
        int lastMatch = lo;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(routeNamesList.get(mid).getTakeOffPoint());
            if (cmp == 0) {
                lastMatch = mid;
                lo = mid + 1;
            } else if (cmp < 0) {
                hi = mid - 1;
            } else {
                break;
            }
        }

        return lastMatch;
    }

    public static ArrayList<String> searchProcess(String airportName, ArrayList<Route> routeNamesList) {
        ArrayList<String> destinationNames = new ArrayList<String>();

        Integer[] indices = binarySearch(routeNamesList, airportName);
        for (int i = 0; i < indices.length; i++) {
            if(routeNamesList.get(i).getTakeOffPoint().equals(airportName)) {
                destinationNames.add(routeNamesList.get(i).getLandingPoint());
            }
        }

        return destinationNames;
    }