Olog(n) 折半查找，欧几里得算法，幂运算。
折半查找
int binary_search(int a[], int x) { //折半查找默认数组已经排序 int low = 0, high = a.length() - 1; while (low <= high) { int mid = (low + high) / 2; if (a[mid] < x) low = mid + 1; else if (a[mid] > x) high = mid - 1; else return mid; } return -1; }
欧几里得算法求最大公因数
int gcd(int m, int n) { //m>n while (n != 0) { int yu = m % n; m = n; n = yu; } return m; }
幂运算
int pow_m(int x, int y) { //x的y次 if (y == 0) return 1; if (y == 1) return x; if (y % 2 == 0) return pow_m(x*x, y / 2); if (y % 2 == 1) return x * pow_m(x*x, y / 2); }
O(log(m+n)) 归并排序
float median(vector<int>& nums1,vector<int>& nums2 ) { int x1 = nums1.size(); int x2 = nums2.size(); if (nums1.empty()) { if (nums2.size() % 2 == 0) return (nums2[x2 / 2] + nums2[x2 / 2 - 1]) / 2; if (nums2.size() % 2 != 0) return nums2[x2 / 2]; } if (nums2.empty()) { if (nums1.size() % 2 == 0) return (nums1[x1 / 2] + nums2[x1 / 2 - 1]) / 2; if (nums1.size() % 2 != 0) return nums1[x1 / 2]; } //归并排序 vector<int>c; int i, j, k;//分别为nums1,nums2,c的下标 for (i = 0, j = 0; i < x1&&j < x2;) { if (nums1[i] < nums2[j]) { c.push_back(nums1[i]); i++; } else c.push_back(nums2[j++]); } while (i < x1) { c.push_back(nums1[i++]); } while (j < x2) { c.push_back(nums2[j++]); } int k = c.size(); if (k% 2 == 0) return (c[k / 2] + nums2[k - 1]) / 2; if (k % 2 != 0) return nums1[k / 2]; //归并排序，顺便求了中位数 }
二分查找数组中小于等于某个数的最大的数：
int binary_up_bound(long long a[], int low, int high, long long key) { while (low < high) { int mid = (low + high + 1) / 2; if (a[mid] > key) { high = mid - 1; } else { //a[mid] <= key low = mid; } } if (a[low] <= key) { return low; } else { return -1; } }