geohash 編碼 常用于將二維的經(jīng)緯度轉(zhuǎn)化為字符串，分為兩步：
- 經(jīng)緯度的二進(jìn)制編碼
- base32 轉(zhuǎn)碼
此題考察唯獨的二進(jìn)制編碼岖常。
算法對維度 [-90,90] 通過二分法進(jìn)行無限逼近（取決于所需精度竭鞍，本題精度為6）
注意：
- 本題進(jìn)行二分法逼近過程中只采用 向下取整 來進(jìn)行二分，
- 針對 二分中間值屬于右區(qū)間洽胶。
算法舉例如下：
輸入：80
（1） 區(qū)間 [-90,90] 進(jìn)行二分為 [-90,0),[0,90] ，成為左右區(qū)間，可以確定 80 為右區(qū)間丐怯，標(biāo)記為 1 喷好；
（2） 針對上一步的右區(qū)間 [0,90] 進(jìn)行二分為 [0,45),[45,90] ，可以確定 80 是右區(qū)間响逢，標(biāo)記為 1 绒窑；
（3） 針對 [45,90] 進(jìn)行二分為 [45,67),[67,90] 棕孙，可以確定 80 為右區(qū)間舔亭，標(biāo)記為 1 ；
（4） 針對 [67,90] 進(jìn)行二分為 [67,78),[78,90] 蟀俊，可以確定 80 位右區(qū)間钦铺，標(biāo)記為 1 ；
（5） 針對 [78,90] 進(jìn)行二分為 [89,84),[84,90] 肢预，可以確定 80 位左區(qū)間矛洞，標(biāo)記為 0 ；
（6） 針對 [78,84) 進(jìn)行二分為 [78,81),[81,84) 烫映，可以確定 80 位左區(qū)間，標(biāo)記為 0 ；
已達(dá)精度要求
輸出：111100
#include <iostream>
using namespace std;
/**
* geohash 編碼
* geohash 常用于將二維的經(jīng)緯度轉(zhuǎn)化為字符串，分為兩步：① 經(jīng)緯度的二進(jìn)制編碼 ② base32 轉(zhuǎn)碼
* 此題考察唯獨的二進(jìn)制編碼：算法對維度 [-90,90] 通過二分法進(jìn)行無限逼近（取決于所需精度，本題精度為6）名惩。
* 注意，本題進(jìn)行二分法逼近過程中只采用 向下取整 來進(jìn)行二分，針對 二分中間值屬于右區(qū)間。
* 算法舉例如下：
* 輸入：80
* （1） 區(qū)間 [-90,90] 進(jìn)行二分為 [-90,0),[0,90] 那槽，成為左右區(qū)間，可以確定 80 為右區(qū)間，標(biāo)記為 1 ；
* （2） 針對上一步的右區(qū)間 [0,90] 進(jìn)行二分為 [0,45),[45,90] ，可以確定 80 是右區(qū)間星岗，標(biāo)記為 1 施逾；
* （3） 針對 [45,90] 進(jìn)行二分為 [45,67),[67,90] 蠕搜，可以確定 80 為右區(qū)間，標(biāo)記為 1 祥山；
* （4） 針對 [67,90] 進(jìn)行二分為 [67,78),[78,90] ，可以確定 80 位右區(qū)間摊聋，標(biāo)記為 1 ；
* （5） 針對 [78,90] 進(jìn)行二分為 [89,84),[84,90] 煎源，可以確定 80 位左區(qū)間，標(biāo)記為 0 ；
* （6） 針對 [78,84) 進(jìn)行二分為 [78,81),[81,84) ，可以確定 80 位左區(qū)間，標(biāo)記為 0 ；
* 已達(dá)精度要求
* 輸出：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"; // 二分中間值屬于右區(qū)間 +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
