P124 4.9练习题
3.已知有序表为{3, 5, 7, 8, 11, 15, 22, 23, 27, 29, 33}，求用二分查找法查找27时所需的比较序列和比较次数
// By SnowDream
#include <iostream>
#include <vector>
using namespace std;int compareCount = 0; // 记录比较次数// 打印当前正在比较的子序列
void printSubVector(const vector<int>& a, int low, int high) {cout << "当前比较序列: ";for (int i = low; i <= high; ++i) {cout << a[i] << " ";}cout << endl;
}int binsearch(vector<int>& a, int low, int high, int k) { // 二分查找递归算法if (low <= high) { // 当前区间存在元素时int mid = (low + high) / 2; // 求查找区间的中间位置compareCount++; // 增加比较次数printSubVector(a, low, high); // 打印当前比较的子序列if (k == a[mid]) { // 找到后返回其物理下标midreturn mid;}if (k < a[mid]) { // 当a[mid] > k时，在a[low..mid-1]中递归查找return binsearch(a, low, mid - 1, k);} else { // 当k > a[mid]时，在a[mid+1..high]中递归查找return binsearch(a, mid + 1, high, k);}}else return -1; // 若当前查找区间没有元素时返回-1
}int binsearch(vector<int>& a, int k) { // 二分查找递归算法int n = a.size();return binsearch(a, 0, n - 1, k);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int k = 27;vector<int> a = {3, 5, 7, 8, 11, 15, 22, 23, 27, 29, 33};int i = binsearch(a, k);if (i >= 0)printf("a[%d]=%d\n", i, k);elseprintf("未找到%d元素\n", k);cout << "总共比较了 " << compareCount << " 次" << endl;return 0;
}
4.假设有14个硬币，编号为0-13，其中编号为12的硬币是假币（假币的重量比真币重），给出采用天平称重方法找出该假币的过程
// By SnowDream
#include<bits/stdc++.h>
using namespace std;int findFakeCoin(vector<int>& coins, int start, int end) {if (start == end) {return start; // 如果只剩下一个硬币，则它就是假币}int mid = (start + end) / 2;int leftWeight = 0, rightWeight = 0;// 假设所有硬币都是真的，如果发现假币就调整重量for (int i = start; i <= end; ++i) {if (i <= mid)leftWeight+=coins[i];elserightWeight+=coins[i];}// 根据哪边更重决定下一步搜索的范围if (leftWeight > rightWeight) {return findFakeCoin(coins, start, mid);} else {return findFakeCoin(coins, mid + 1, end);}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);vector<int> coins(14, 0); // 初始化所有硬币为真coins[12] = 1; // 设置第12个硬币为假int fakeCoinIndex = findFakeCoin(coins, 0, 13);cout << "假币的编号是: " << fakeCoinIndex << endl;return 0;
}
5.有一个递增有序序列（1,3,5,6,8,10,12），给出查找k=2的插入点的过程
// By SnowDream
#include<bits/stdc++.h>
using namespace std;// 二分查找找到k的插入点
int findInsertionPoint(const vector<int>& nums, int k) {int low = 0, high = nums.size() - 1;int mid;while (low <= high) {mid = low + (high - low) / 2; // 防止溢出if (nums[mid] < k) {low = mid + 1;} else {high = mid - 1;}}return low; // 返回插入点
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);vector<int> nums = {1, 3, 5, 6, 8, 10, 12};int k = 2;int insertionPoint = findInsertionPoint(nums, k);cout << "值 " << k << " 的插入点是：" << insertionPoint << endl;return 0;
}
P108
例4.3 计算右侧小于当前元素的个数（Leetcode315）
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
// By SnowDream
#include<bits/stdc++.h>
using namespace std;void mergeSort(vector<int>& nums, vector<int>& indexs, vector<int>& tempindexs,vector<int>& res, int left, int right) {if (left >= right) return;int mid = left + (right - left) / 2;mergeSort(nums, indexs, tempindexs, res, left, mid);// 递归排序左半部分mergeSort(nums, indexs, tempindexs, res, mid + 1, right);// 递归排序右半部分int i = left, j = mid + 1, t = 0; // 合并两个已排序的部分while (i <= mid && j <= right) {if (nums[indexs[i]] > nums[indexs[j]]) {for (int k = i; k <= mid; k++) {// 计算右侧元素小于左侧元素的个数res[indexs[k]] += (j - mid);}tempindexs[t++] = indexs[j++];} else {tempindexs[t++] = indexs[i++];}}while (i <= mid) { // 将剩余元素复制到临时数组中tempindexs[t++] = indexs[i++];}while (j <= right) {tempindexs[t++] = indexs[j++];}for (int k = left; k <= right; k++) {// 将临时数组中的元素复制回原数组indexs[k] = tempindexs[k - left];}
}vector<int> countSmaller(vector<int>& nums) {vector<int> res(nums.size(), 0); // 保存结果vector<int> indexs(nums.size()); // 索引数组for (int i = 0; i < indexs.size(); i++) { // 初始化索引数组indexs[i] = i;}vector<int> tempindexs(indexs.size(), 0); // 临时数组mergeSort(nums, indexs, tempindexs, res, 0, nums.size() - 1);return res;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);vector<int> nums = {5, 2, 6, 1};vector<int> ans = countSmaller(nums);cout << "每个元素右侧比当前元素小的元素个数：";for (int num : ans) {cout << num << " ";}return 0;
}
P111
例4.5 设计一个算法求给定的两个有序序列的中位数
示例
输入：a=(11,13,15,17,19) b=(2,4,6,8,20)
输出 : 11
// By SnowDream
#include<bits/stdc++.h>
using namespace std;// 求a[s..t]序列的前半子序列
void prepart(int &s, int &t) {int m = (s + t) / 2;t = m;
}// 求a[s..t]序列的后半子序列
void postpart(int &s, int &t) {int m = (s + t) / 2;if ((t - s + 1) % 2 == 1) // 序列中有奇数个元素s = m;else // 序列中有偶数个元素s = m + 1;
}// 找到两个数组的中位数
int midnum(const int a[], int s1, int t1, const int b[], int s2, int t2) {if (s1 == t1 && s2 == t2) // 均只有一个元素时返回较小者return min(a[s1], b[s2]);else {int m1 = (s1 + t1) / 2; // 求a的中位数int m2 = (s2 + t2) / 2; // 求b的中位数if (a[m1] == b[m2]) // 两中位数相等时返回该中位数return a[m1];if (a[m1] < b[m2]) { // 当a[m1]<b[m2]时postpart(s1, t1); // a取后半部分prepart(s2, t2); // b取前半部分return midnum(a, s1, t1, b, s2, t2);} else { // 当a[m1]>b[m2]时prepart(s1, t1); // a取前半部分postpart(s2, t2); // b取后半部分return midnum(a, s1, t1, b, s2, t2);}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int a[] = {11, 13, 15, 17, 19};int b[] = {2, 4, 6, 8, 20};int n = sizeof(a) / sizeof(a[0]);cout << "中位数: " << midnum(a, 0, n - 1, b, 0, n - 1) << "\n";return 0;
}