并不是只有有序的数组才能用二分查找,只要数组具有二段性,也就是根据某个规则可以分为两段,就可以用二分。
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else if (nums[mid] > target) r = mid - 1;
else return mid;
}
return -1;
}
};


class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
if (n == 0 || target < nums[0] || target > nums[n - 1]) return {-1, -1};
int begin, l = 0, r = n - 1;
// 1.找左端点
while (l < r) // ==会死循环
{
int mid = l + (r - l) / 2; // 向下取整
if (target > nums[mid]) l = mid + 1;
else r = mid;
}
// 2.可能没有目标值
if (nums[l] != target) return {-1, -1};
else begin = l;
l = 0, r = n - 1;
// 3.找右端点
while (l < r)
{
int mid = l + (r - l + 1) / 2; // 向上取整
if (target < nums[mid]) r = mid - 1;
else l = mid;
}
return {begin, l};
}
};
为什么最后可以直接
return l,如果没找到目标值,则会由l > r出循环。如果是由r = mid - 1出的循环,说明此时mid == l且所指位置就是要插入的位置;如果是由l = mid + 1出的循环,mid所指的元素刚好小于目标值,则出循环后l所指的就是需要插入的位置。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (target < nums[mid]) r = mid - 1;
else if (target > nums[mid]) l = mid + 1;
else return mid;
}
return l;
}
};

class Solution {
public:
int mySqrt(int x) {
if (x < 1) return 0;
int l = 1, r = x;
while (l < r)
{
long long mid = l + (r - l + 1) / 2;
if (mid * mid <= x) l = mid;
else r = mid - 1;
}
return l;
}
};

不是只有有序数组才能用二分算法,只要数组存在二段性,也就是可以按一定的规则分为两部分,都可以抽象的用二分算法解决问题。 本题就是把数组分为升序和降序两部分。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int l = 1, r = arr.size() - 2;
while (l < r)
{
int mid = l + (r - l + 1) / 2;
if (arr[mid] > arr[mid - 1]) l = mid; // 升序
else r = mid - 1;
}
return l;
}
};

class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (nums[mid] > nums.back()) l = mid + 1;
else r = mid;
}
return nums[l];
}
};
排序数组中的搜索问题,首先想到的就是二分解法。
class Solution {
public:
int takeAttendance(vector<int>& records) {
int l = 0, r = records.size() - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (records[mid] > mid) r = mid;
else l = mid + 1;
}
return l == records[l] ? l + 1 : l; // 有可能缺席的是最后一位同学
}
};
要分到恰好符合题意不太容易,可以换一种思路,枚举符合题目要求的情况下每组最可能多的人数,再用二分优化。
#include <iostream>
#include <unordered_map>
using namespace std;
int n, m;
int a[100001];
unordered_map<int, int> hashmap;
bool check(int x)
{
int g = 0;
for (auto [a, b] : hashmap)
{
g += b / x + (b % x == 0 ? 0 : 1);
}
if (g <= m) return true;
else return false;
}
int main()
{
cin >> n >> m;
int maxcount = 0;
for (int i = 0; i < n; i++)
{
int x; cin >> x;
maxcount = max(maxcount, ++hashmap[x]);
}
if (hashmap.size() > m) cout << -1 << endl;
else
{
int l = 0, r = maxcount;
while (l < r)
{
int mid = l + (r - l) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
return 0;
}本篇文章的分享就到这里了,如果您觉得在本文有所收获,还请留下您的三连支持哦~