Lintcode 530. Geohash II

This is a followup question for Geohash.

Convert a Geohash string to latitude and longitude.

Try http://geohash.co/.

Check how to generate geohash on wiki: Geohash or just google it for more details.

Example

Example1

Input: "wx4g0s"`
Output: lat = 39.92706299 and lng = 116.39465332

Example2

Input: "w"
Output: lat = 22.50000000 and lng = 112.50000000

Code (Java):

public class GeoHash {
    /*
     * @param geohash: geohash a base32 string
     * @return: latitude and longitude a location coordinate pair
     */
    public double[] decode(String geohash) {
        // step1: get binary code
        //
        String binaryGeoHash = getBinaryGeoHash(geohash);

        // step 2: get binary representation of the long and latitude
        String[] binaryLongLati = getBinaryLongAndLati(binaryGeoHash);

        double longtitude = getLocation(binaryLongLati[0], -180, 180);
        double latitude = getLocation(binaryLongLati[1], -90, 90);

        double[] ans = new double[2];
        ans[0] = latitude;
        ans[1] = longtitude;

        return ans;
    }

    private double getLocation(String code, double start, double end) {
        double mid = start + (end - start) / 2;
        for (int i = 0; i < code.length(); i++) {
            if (code.charAt(i) == '0') {
                end = mid;
            } else {
                start = mid;
            }

            mid = start + (end - start) / 2;
        }

        return mid;
    }

    private String[] getBinaryLongAndLati(String binaryGeoHash) {
        String[] ans = new String[2];
        StringBuilder longtitude = new StringBuilder();
        StringBuilder latitude = new StringBuilder();

        for (int i = 0; i < binaryGeoHash.length(); i += 2) {
            longtitude.append(binaryGeoHash.charAt(i));
            if (i + 1 < binaryGeoHash.length()) {
                latitude.append(binaryGeoHash.charAt(i + 1));
            }
        }

        ans[0] = longtitude.toString();
        ans[1] = latitude.toString();

        return ans;
    }

    private String getBinaryGeoHash(String geohash) {
        String dict = "0123456789bcdefghjkmnpqrstuvwxyz";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < geohash.length(); i++) {
            int base32 = dict.indexOf(geohash.charAt(i));
            sb.append(toBase2(base32));
        }

        return sb.toString();
    }

    private String toBase2(int num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            sb.insert(0, num % 2);
            num /= 2;
        }
        
        // pad with zeros
        while (sb.length() < 5) {
            sb.insert(0, '0');
        }

        return sb.toString();
    }
}