如何在 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）

由于每个arraylist中有很多机场名称和航线，大小在30000以上，所以我不得不使用二分查找来实现代码优化。

我已经在不使用二进制搜索的情况下完成了这个过程。

如何通过二进制搜索来完成？

下面是我的代码片段。

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

Airpot 名称

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;
    }

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

How to implement binary Search process in Arraylist in Java

java

arraylist

binary-search