GeoHash 编码

geohash 编码 常用于将二维的经纬度转化为字符串，分为两步：

• 经纬度的二进制编码
• base32 转码

此题考察唯独的二进制编码。

算法对维度 [-90,90] 通过二分法进行无限逼近（取决于所需精度，本题精度为6）

注意：

• 本题进行二分法逼近过程中只采用 向下取整 来进行二分，
• 针对 二分中间值属于右区间。

算法举例如下：

输入：80
（1） 区间 [-90,90] 进行二分为 [-90,0),[0,90] ，成为左右区间，可以确定 80 为右区间，标记为 1 ；
（2） 针对上一步的右区间 [0,90] 进行二分为 [0,45),[45,90] ，可以确定 80 是右区间，标记为 1 ；
（3） 针对 [45,90] 进行二分为 [45,67),[67,90] ，可以确定 80 为右区间，标记为 1 ；
（4） 针对 [67,90] 进行二分为 [67,78),[78,90] ，可以确定 80 位右区间，标记为 1 ；
（5） 针对 [78,90] 进行二分为 [89,84),[84,90] ，可以确定 80 位左区间，标记为 0 ；
（6） 针对 [78,84) 进行二分为 [78,81),[81,84) ，可以确定 80 位左区间，标记为 0 ；
已达精度要求
输出：111100

#include <iostream>

using namespace std;

/**
 * geohash 编码
 * geohash 常用于将二维的经纬度转化为字符串，分为两步：① 经纬度的二进制编码 ② base32 转码
 * 此题考察唯独的二进制编码：算法对维度 [-90,90] 通过二分法进行无限逼近（取决于所需精度，本题精度为6）。
 * 注意，本题进行二分法逼近过程中只采用 向下取整 来进行二分，针对 二分中间值属于右区间。
 * 算法举例如下：
 * 输入：80
 * （1） 区间 [-90,90] 进行二分为 [-90,0),[0,90] ，成为左右区间，可以确定 80 为右区间，标记为 1 ；
 * （2） 针对上一步的右区间 [0,90] 进行二分为 [0,45),[45,90] ，可以确定 80 是右区间，标记为 1 ；
 * （3） 针对 [45,90] 进行二分为 [45,67),[67,90] ，可以确定 80 为右区间，标记为 1 ；
 * （4） 针对 [67,90] 进行二分为 [67,78),[78,90] ，可以确定 80 位右区间，标记为 1 ；
 * （5） 针对 [78,90] 进行二分为 [89,84),[84,90] ，可以确定 80 位左区间，标记为 0 ；
 * （6） 针对 [78,84) 进行二分为 [78,81),[81,84) ，可以确定 80 位左区间，标记为 0 ；
 * 已达精度要求
 * 输出：111100
 * @param n 维度 latitude
 * @return 维度编码
 */
string geohash(int n) {
    int left = -90, right = 90;

    // 处理边界值
    if (n == right) return "1";
    if (n == left) return "0";

    // 不在边界，再编码
    string encode;
    while (right - left >= 6) {
        int mid = (left + right) / 2;

        // 找到了，未找到
        if (n == mid) {
            encode += "1"; // 二分中间值属于右区间 +1
            return encode;
        }

        // 二分限范围
        if (n > mid) {
            encode += "1";
            left = mid;
        } else {
            encode += "0";
            right = mid;
        }
    }
    return encode;
}

int main() {
    cout << geohash(80);
    return 0;
}

111100