Lookup zip codes in list of ranges-CodePudding

I've a list of zip code ranges, such that one region can multiple zip codes.

class Zip {

    Long rangeStart;    // zip code range first
    Long rangeEnd;      // zip code range last
    String regionName;
}

Input 1: List<Zip> zipList Input 2: Long zipCodeToSearch

There are NO overlapping ranges.

I've to design a solution where when user inputs a zip code I've to lookup the List<Zip> and return its region name.

I've to solve it for both when the zipList is sorted as well as when it is unsorted.

My solution when zipList is sorted using Binary search:

Create a HashMap<Integer, String> storing an index & region name. e.g.

1 -> Hawaii
2 -> LA
3 -> NY

Create a list storing start and end of the range. i.e.

List<Long> rangeList;
for (Zip zip : zipList) {
    rangeList.add(zip.rangeStart);
    rangeList.add(zip.rangeEnd);
}

Using binary search iteratively check if zipCodeToSearch is within mid and its neighbor.

And by neighbor, I mean I'll check both left and right as in binary search. If result is found return map.get(mid/2)

My solution when zipList is unsorted:

This is basically linear search and I'm checking like:

for (int i = 1; i < rangeList.size(); i  = 2) {
    if (rangeList.get(i - 1) <= zipCodeToSearch && zipCodeToSearch <= rangeList.get(i)) {
        return i / 2;
    }
}

Are there any better solution?

CodePudding user response：

Iterate the Zip list

static Zip getZip(List<Zip> zipList, long range) {
    for (Zip zip: zipList)
        if (range >= zip.rangeStart && range <= zip.rangeEnd)
            return zip;
}

CodePudding user response：

You can add a method to your Zip class to check if a zip code is within range:

class Zip {
    Long rangeStart;
    Long rangeEnd;
    String regionName;

    public boolean isInRange(long zip) {
        return zip >= rangeStart && zip <= rangeEnd;
    }
}

Then you can stream and filter the zipList to get the region name:

public static String findRegionName(List<Zip> zipList, long searchZip) {
    return zipList.stream().filter(zip -> zip.isInRange(searchZip))
            .map(Zip::getRegionName).findAny().orElse(null);
}