有序数组中找x[i]==i的数i
若数组中无重复值，索引值以1增加、数组值以>=1增加。当midVal<midIdx时搜右边[midIdx+1, u]，当midVal>midIdx时搜左边[l, midIdx-1]。
若数组中有重复值，索引值以1增加、数组值以>=0增加。当midVal<midIdx时除了搜右边[midIdx+1, u]，因为左边可以同值重复，也要搜左边[l, midVal]。同理，midVal>midIdx时除了搜左边[l, midIdx-1]，也要搜右边[midVal, u]。
简化：当midVal!=midIdx时，搜索的左边范围可统一成[l, min{midIdx-1, midVal}]。因为当midVal<midIdx时，min{midIdx-1, midVal}=midVal；当midVal>midIdx时，min{midIdx-1, midVal}=midIdx-1。同理，右边范围可统一成[max{ midIdx+1, midVal }, u]。
所以，当midVal!=midIdx时，要搜[l, min{midIdx-1, midVal}]和[max{ midIdx+1, midVal }, u]。直观上，合并使搜索范围尽量小。
有序数组中找值t，该有序数组不知size()只知elementAt()
不知size()就没法取得中位数，可假设该数组后部空位上都是∞，令elementAt()返回-1表示该位置的值太大。见ctci p400
int search(Listy list, int value) {
int idx = 1;
while (list.elementAt(idx) != -1 && list.elementAt(idx) < value) {
idx *= 2;
}
return binarySearch(list, value, idx / 2, idx);
}
int binarySearch(Listy list, int target, int l, int u) {
while (l <= u) {
int m = l + (u - l) / 2;
int val = list.elementAt(m);
if (val == -1 || val > target) {
u = m - 1;
} else if (val < target) {
l = m + 1;
} else {
return m;
}
}
return -1;
}
有序数组中散布着无用数据
若尝试的mid位置是无用数据，则mid一圈圈往左右扩展，用最近的有用元素替代。见ctci p401
int mid = l + (u - l) / 2;
if (strs[mid].isEmpty()) { // mid是无用数据
int left = mid - 1, right = mid + 1;
while (true) {
if (left < l && right > u) { // 找不到有用数据
return -1;
}
if (left >= l && !strs[left].isEmpty()) { // 左看一步
mid = left;
break;
}
if (right <= u && !strs[right].isEmpty()) { // 右看一步
mid = right;
break;
}
left--;
right++;
}
}
...
x的平方根
int mySqrt(int x) {
if (x <= 1) return x;
// 找满足r^2<=x的最大整数r，就是找满足r^2>x的最小整数r的前一个数
int l = 1, u = x;
while (l + 1 < u) {
int mid = l + (u - l) / 2;
if (mid > x / mid) { // mid*mid > x
u = mid;
} else {
l = mid;
}
}
return l;
}
num是完全平方数
bool isPerfectSquare(int num) {
// 找到使x*x>=num的第一个x，二分搜索
int l = 1, u = num;
while (l <= u) {
int mid = l + (u - l) / 2;
if (mid >= num / mid) { // mid*mid >= num
u = mid - 1;
} else {
l = mid + 1;
}
}
return l * l == num;
}
找数组中任一峰值
int findPeakElement(vector<int>& nums) {
// 只要不断往高处走，就一定有波峰，这是一种单调性
// 找波峰，找第一个nums[i]>nums[i+1]的位置i
// i二分搜索的范围是[0..N-2]
const int N = nums.size();
int l = -1, u = N - 1;
while (l + 1 < u) {
int mid = l + (u - l) / 2;
if (nums[mid] > nums[mid+1]) {
u = mid;
} else {
l = mid;
}
}
return u;
}
在先升后降的山坡数组中找数
int findInMountainArray(int target, MountainArray &mountainArr) {
// 二分搜索，先找峰值，再分别找左右半数组
// 找第一个A[m]>A[m+1]的位置m，m在[1..N-2]
const int N = mountainArr.length();
int l = 0, u = N - 1;
while (l + 1 < u) {
int m = l + (u - l) / 2;
if (mountainArr.get(m) > mountainArr.get(m + 1)) {
u = m;
} else {
l = m;
}
}
// u是波峰
int ans = binarySsearch(target, mountainArr, 0, u, true);
if (ans != -1) return ans;
return binarySsearch(target, mountainArr, u, N - 1, false);
}
int binarySsearch(int target, MountainArray &mountainArr,
int lower, int upper, bool asc) {
int l = lower, u = upper;
while (l <= u) {
int m = l + (u - l) / 2;
int val = mountainArr.get(m);
if (target == val) return m;
if ((target < val) == asc) {
u = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
满足x!末尾刚好K个0的数x有多少个
int preimageSizeFZF(int K) {
// 题目：满足x!末尾刚好K个0的数x有多少个？
// x!末尾0的个数等于因子5的个数，因子5的个数每连续5个数相等。
// 因此，满足条件的x若存在就有5个，若不存在就0个。
// 二分搜索猜x是否存在，x的上限取5K，因为5K可至少贡献5K/5=K个因子5。
long l = 0, u = 5l * K;
while (l <= u) {
long mid = l + (u - l) / 2;
int count = countZeros(mid);
if (count == K) return 5;
if (count > K) u = mid - 1;
else l = mid + 1;
}
return 0;
}
int countZeros(long n) {
int ans = 0;
while (n /= 5) {
ans += n;
}
return ans;
}
有序数组中找k个最接近x的元素
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
// 设要找的子段为 arr[i..i+k-1]，对位置i做二分搜索
// 比较 arr[i] 和 子段后的arr[i+k]：
// 若 x - arr[i] > arr[i+k] - x，右移子段起始i
int lo = 0, hi = (int)arr.size() - k;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (x - arr[mid] > arr[mid + k] - x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return vector<int>(begin(arr) + lo, begin(arr) + lo + k);
}