二分查找

Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array II

Preimage Size of Factorial Zeroes Function

注意點:

1. 不要用mid = (lo + hi)/2, 容易溢出, 應該使用 mid = lo + (hi - lo) / 2

Find Minimum in Rotated Sorted Array

題意: 將一排序的數組旋轉後，需要找到最小的元素，假定數組中沒有重複的數

class Solution {public: int findMin(vector<int>& nums) { int lo = 0, hi = nums.size() - 1; while (lo < hi) { if (nums[lo] < nums[hi]) return nums[lo]; int mid = lo + (hi - lo) / 2; if (nums[mid] > nums[hi]) lo = mid + 1; // mid一定不是 else hi = mid; // mid可能是 } return nums[lo]; }};

Find Minimum in Rotated Sorted Array II

題意: 在上面一題的基礎上要求元素可能重複

1 0 1 1 1 // 0 在左半部分1 1 1 0 1 // 0 在右半部分也就是說如果兩端的元素相等時，最小值既可能在左半部分也可能在右半部分

思路: 如果兩端的元素相等，將lo前進1步

class Solution {public: int findMin(vector<int>& nums) { int lo = 0, hi = nums.size() - 1; while (lo < hi) { if (nums[lo] < nums[hi]) return nums[lo]; int mid = lo + (hi - lo) / 2; if (nums[mid] > nums[hi]) lo = mid + 1; else if (nums[mid] < nums[hi]) hi = mid; else lo ++; } return nums[lo]; }};

Preimage Size of Factorial Zeroes Function

題意: x! 後面有k個0，求有多少個x，其x!後面有k個0

觀察:

1. 2*5才等於10，2取之不盡用之不竭~, 0的個數等價於5的個數
2. n!中5的個數等於 n/5 + n/5/5 + ... n/5/5/5/5/5 ...
3. 二分查找最小的後面有k+1個0的數與k個0的數

class Solution {public: int preimageSizeFZF(int K) { return find_lower(K+1) - find_lower(K); } int find_lower(long long k) { long long lo = 0, hi = k * 5; while (lo < hi) { long long mid = lo + (hi - lo) / 2; long long count = 0, tmp = mid; while (tmp / 5) { count += tmp / 5; tmp /= 5; } if (count < k) lo = mid + 1; else hi = mid; } return lo; }};

推薦閱讀：