当前位置：网站首页>二分查找符合要求的值及局部最小值
二分查找符合要求的值及局部最小值
2022-04-21 10:28:00 【明朗晨光】
1、有序数组中找到 num
#include <iostream>
#include <time.h>
using namespace std;
//arr中查找num
bool find(int arr[], int len, int num) {
if (len == 0) return false;
int l = 0;
int r = len - 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] == num) {
return true;
} else if (arr[mid] > num) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return false;
}
bool test(int sortedArr[], int len, int num) {
for (int i = 0; i < len; i++) {
if (sortedArr[i] == num)
return true;
}
return false;
}
int main() {
int testTime = 500000;
int maxSize = 20;
int maxValue = 100;
bool succeed = true;
srand(time(0));
for (int i = 0; i < testTime; i++) {
//生成随机数组
int len = rand() % maxSize;
int *arr = new int[len];
for (int j = 0; j < len; j++) {
arr[j] = rand() % maxValue;
}
//调用系统sort方法进行排序 —— 有序数组
sort(arr, arr + len);
//随机值
int value = (rand() % (maxValue + 1)) - (rand() % maxValue);
if (test(arr, len, value) != find(arr, len, value)) {
cout << "出错了!" << endl;
succeed = false;
break;
}
}
cout << (succeed ? "Nice!" : "Fucking fucked!") << endl;
return 0;
}
2、有序数组中找到 >=num 最左的位置
#include <iostream>
#include <time.h>
using namespace std;
//>=num最左位置
int mostLeftNoLessNumIndex(int arr[], int len, int num) {
if (len == 0)
return -1;
int l = 0;
int r = len - 1;
int ans = -1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] >= num) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
int test(int arr[], int len, int num) {
for (int i = 0; i < len; i++) {
if (arr[i] >= num)
return i;
}
return -1;
}
void printArray(int arr[], int len) {
for (int i = 0; i < len; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int testTime = 500000;
int maxLen = 10;
int maxValue = 100;
bool succeed = true;
srand(time(0));
for (int i = 0; i < testTime; i++) {
int len = rand() % (maxLen + 1);
int *arr = new int[len];
for (int j = 0; j < len; j++) {
arr[j] = rand() % maxValue;
}
sort(arr, arr + len);
int val = (rand() % (maxValue + 1)) - (rand() % maxValue);
if (test(arr, len, val) != mostLeftNoLessNumIndex(arr, len, val)) {
printArray(arr, len);
cout << val << endl;
cout << test(arr, len, val) << endl;
cout << mostLeftNoLessNumIndex(arr, len, val) << endl;
succeed = false;
break;
}
}
cout << (succeed ? "Succeed!" : "Failed!") << endl;
return 0;
}
3、有序数组中找到<=num最右的位置
#include <iostream>
#include <time.h>
using namespace std;
//<=num最右位置
int mostRightNoMoreNumIndex(int arr[], int len, int num) {
if (len == 0)
return -1;
int l = 0;
int r = len - 1;
int ans = -1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] <= num) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
int test(int arr[], int len, int num) {
for (int i = len - 1; i >= 0; i--) {
if (arr[i] <= num)
return i;
}
return -1;
}
void printArray(int arr[], int len) {
for (int i = 0; i < len; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int testTime = 500000;
int maxLen = 10;
int maxValue = 100;
bool succeed = true;
srand(time(0));
for (int i = 0; i < testTime; i++) {
int len = rand() % (maxLen + 1);
int *arr = new int[len];
for (int j = 0; j < len; j++) {
arr[j] = rand() % maxValue;
}
sort(arr, arr + len);
int val = (rand() % (maxValue + 1)) - (rand() % maxValue);
if (test(arr, len, val) != mostRightNoMoreNumIndex(arr, len, val)) {
printArray(arr, len);
cout << val << endl;
cout << test(arr, len, val) << endl;
cout << mostRightNoMoreNumIndex(arr, len, val) << endl;
succeed = false;
break;
}
}
cout << (succeed ? "Succeed!" : "Failed!") << endl;
return 0;
}
4、局部最小值问题
无序数组，任意两个相邻的数不相等，返回其中一个局部最小值。
局部最小值的定义：
- arr[0] < arr[1]，则 arr[0] 是局部最小
- arr[n - 2] > arr[n - 1]，则 arr[n-1]是局部最小
- arr[i] < arr[i + 1] 且 arr[i] < arr[i - 1]，则 arr[i] 是局部最小
【思路】
- 如果arr[0] < arr[1]，直接返回arr[0]，否则说明arr[0] > arr[1]，因为相邻数不相等；
- 如果arr[n - 1] < arr[n - 2]，直接返回arr[n - 1]，否则arr[n - 1] > arr[n - 2]；
- 那么，在 arr[0] arr[1] 这个小局部，是下降的；而 arr[n - 2] arr[n-1] 这个局部是上升的。因此可以断定，0 ~ n - 1 范围上必然存在局部最小（这个结论的前提必须是数组的相邻位置不相等，曲线才会变化起来），于是可以利用这个结论；
- 首先找到 mid 位置，如果 arr[mid] < arr[mid - 1] 且 arr[mid] < arr[mid + 1]，那么返回 arr[mid]，否则 arr[mid] 一定是大于arr[mid-1] 或者 arr[mid + 1] 的，假设此时的情况是 arr[mid - 1] < arr[mid]，那么在 arr[mid - 1] arr[mid] 这个小局部，又是上升的，上升的情况又出现了，此时可以说在 0 ~ mid范围上必然存在局部最小值。
- 总结来说，就是在 0 ~ n - 1 范围上找 mid，如果 arr[mid] 刚好比它的左右邻居都小，则直接返回，否则找比 arr[mid] 小的一侧，砍掉另一侧，即进行二分。
- 注意：当比较的局部个数小于3个的情况。
【代码】
#include <iostream>
using namespace std;
int oneMinIndex(int arr[], int len) {
if (len == 0)
return -1;
if (len == 1)
return 0;
if (arr[0] < arr[1])
return 0;
if (arr[len - 1] < arr[len - 2])
return len - 1;
int l = 0;
int r = len - 1;
//确保比较范围的数个数 >= 3
while (l < (r - 1)) {
int mid = l + ((r - l) >> 1);
if (arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1])
return mid;
else {
if (arr[mid] > arr[mid - 1]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return arr[l] < arr[r] ? l : r;
}
// 也用于测试
bool check(int arr[], int len, int minIndex) {
if (len == 0) {
return minIndex == -1;
}
int left = minIndex - 1;
int right = minIndex + 1;
bool leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
bool rightBigger = right < len ? arr[right] > arr[minIndex] : true;
return leftBigger && rightBigger;
}
void printArray(int arr[], int len) {
for (int i = 0; i < len; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int testTime = 1000000;
int maxLen = 100;
int maxValue = 200;
srand(time(0));
cout << "测试开始:" << endl;
for (int i = 0; i < testTime; i++) {
//生成随机数组，且相邻数不相等
int len = rand() % maxLen;
int *arr = new int[len];
if (len > 0) {
arr[0] = rand() % maxValue;
for (int i = 1; i < len; i++) {
do {
arr[i] = rand() % maxValue;
} while (arr[i] == arr[i - 1]);
}
}
int ans = oneMinIndex(arr, len);
if (!check(arr, len, ans)) {
cout << "出错了!" << endl;
printArray(arr, len);
cout << ans << endl;
break;
}
}
cout << "测试结束" << endl;
return 0;
}
【启示】
二分操作不一定要数组有序，只要确定某个时刻一定有一个值，就可以使用二分。
版权声明
本文为[明朗晨光]所创，转载请带上原文链接，感谢
https://blog.csdn.net/u011386173/article/details/124313802
边栏推荐
猜你喜欢
HMS Core 6.4.0版本发布公告
MKL and vs2019 configuration method
Pytorch梯度检查 torch.autograd.gradcheck
2022信息与未来预备刷题1《New Online Judge 1112: 平面分割》
24 pictures to conquer border image
Digital economy - new economy index (2017-2022) & two dimensional indicators of digital economy calculation of 31 provinces (2013-2020)
5_数据分析—数据可视化
Release announcement of HMS core version 6.4.0
2022信息与未来预备刷题2《New Online Judge 1113: 位数问题》
uniapp 微信小程序 点击按钮调用微信支付
随机推荐
SQL: SQL file of tree three-tier occupational classification table
zsh: segmentation fault 解决方法
MKL and vs2019 configuration method
L1-046 整除光棍 (20 分)
Transaction isolation level and mvcc
C＃入门-利用正则表达式校验身份证号
Better than SQL, another domestic database language was born
阿里云移动研发平台EMAS，3月产品动态
自动化运维平台未来的发展前景？
Impact of AOT and single file release on program performance
torch文件保存与加载——【torch学习笔记】
Talk about the safety factor of futures online account opening
大力飞砖之DFS（树的创建）
“空气洗”再迎迭代，模仿者又有了新目标
"Air washing" meets the iteration again, and the imitator has a new goal
[software test series IX] description of matters to be provided for pressure test application
Filebeat收集日志数据传输到Redis，通过Logstash来根据日志字段创建不同的ES索引
摩尔线程与Ampere Computing达成合作
Ansible_ 03_ Advanced Playbook
L1-050 倒数第N个字符串 (15 分)