二分法
/*
* 完全二叉树编号从1开始
* 如果第k个节点位于第h层，则k的二进制表示包含h+1位，
* 其中最高位是1，其余各位从高到低表示从根节点到第k个节点的路径，
* 0表示移动到左子节点，1表示移动到右子节点。
* 通过位运算得到第k个节点对应的路径，判断该路径对应的节点是否存在，即可判断第k个节点是否存在。
*/
bool exist(struct TreeNode *root, int height, int k) {
// 树高height（从1开始），从根到叶节点需要往下走height-1次
int count = height - 1;
while (count-- > 0) {
if (root == NULL) break;
// 从第二位开始，根据每一位判断往左往右
int bit = ((k >> count) & 1);
if (bit == 0) {
root = root->left;
} else {
root = root->right;
}
}
// 返回是否存在
return root != NULL;
}
int binarySearch(struct TreeNode *root, int height, int left, int right) {
int mid;
// 找最后一个节点的编号
while (left <= right) {
mid = (right - left) / 2 + left;
if (exist(root, height, mid)) {
// 若这个编号为mid的节点存在，往右找
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
// 完全二叉树的节点个数
int countNodes(struct TreeNode *root) {
if (root == NULL) return 0;
struct TreeNode *node = root;
int height = 0;
while (node != NULL) {
height++;
node = node->left;
}
// 最下层，最左边的节点编号
int left = (1 << (height - 1));
// 最下层，最右边的节点编号
int right = (1 << height) - 1;
return binarySearch(root, height, left, right);
}
int cmp(const void *a, const void *b) {
return (*(int *) a - *(int *) b);
}
// 找左边界
int findLeft(int *nums, int left, int right, int target) {
int mid;
while (left <= right) {
mid = (right - left) / 2 + left;
if (nums[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
// 找右边界
int findRight(int *nums, int left, int right, int target) {
int mid;
while (left <= right) {
mid = (right - left) / 2 + left;
if (nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return right;
}
// 排完序后找左右边界
int *targetIndices(int *nums, int numsSize, int target, int *returnSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int left = findLeft(nums, 0, numsSize - 1, target);
int right = findRight(nums, 0, numsSize - 1, target);
int count = right - left + 1;
*returnSize = 0;
if (count <= 0)return NULL;
int *res = (int *) malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i) {
res[(*returnSize)++] = left + i;
}
return res;
}
int countPos(int *array, int start, int end) {
// 全是非正数
if (array[end] <= 0) return 0;
// 左右边界
int i;
int j = end;
int left = start, right = end;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] > 0)
right = mid - 1;
else
left = mid + 1;
}
i = left;
return j - i + 1;
}
int countNeg(int *array, int start, int end) {
// 全是非负数
if (array[start] >= 0) return 0;
// 左右边界
int i = start;
int j;
int left = start, right = end;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] >= 0)
right = mid - 1;
else
left = mid + 1;
}
j = right;
return j - i + 1;
}
int maximumCount(int *nums, int numsSize) {
int i = countPos(nums, 0, numsSize - 1);
int j = countNeg(nums, 0, numsSize - 1);
return i > j ? i : j;
}
// 在非递增序列中找-1插入的左边界
int findPosition(int *array, int left, int right) {
int mid;
int target = -1;
while (left <= right) {
mid = (right - left) / 2 + left;
if (array[mid] <= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
// 一行行统计，没有利用到列也是非递增的条件
int countNegatives(int **grid, int gridSize, int *gridColSize) {
int res = 0;
for (int i = 0; i < gridSize; ++i) {
res += gridColSize[i] - findPosition(grid[i], 0, gridColSize[i] - 1);
}
return res;
}
// 在非递增序列中找-1插入的左边界
int findPosition(int *array, int left, int right) {
int mid;
int target = -1;
while (left <= right) {
mid = (right - left) / 2 + left;
if (array[mid] <= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
// 每一行从前往后第一个负数的位置是不断递减的
// 右边界也就是-1插入的位置，也就是负数应该出现的位置，下标不断减小。没必要每次都以gridSize作为二分法右边界
int countNegatives(int **grid, int gridSize, int *gridColSize) {
int res = 0;
int tempPos = gridColSize[0];
int temp;
// 处理每行
for (int i = 0; i < gridSize; ++i) {
// 下标从0到第一个负数出现的位置
temp = findPosition(grid[i], 0, tempPos - 1);
res += gridColSize[i] - temp;
// 更新第一个负数的下标
tempPos = temp;
}
return res;
}
int cmp(const void *a, const void *b) {
return (*(int *) a - *(int *) b);
}
// 找右边界
int binarySearch(int *array, int left, int right, int target) {
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] <= target)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
int *answerQueries(int *nums, int numsSize, int *queries, int queriesSize, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * queriesSize);
*returnSize = queriesSize;
qsort(nums, numsSize, sizeof(int), cmp);
// 保存前缀和
int sum[numsSize];
sum[0] = nums[0];
for (int i = 1; i < numsSize; ++i) {
sum[i] = sum[i - 1] + nums[i];
}
// 在前缀和数组里二分查找
for (int i = 0; i < queriesSize; ++i) {
res[i] = binarySearch(sum, 0, numsSize - 1, queries[i]) + 1;
}
return res;
}
// todo
int peakIndexInMountainArray(int *arr, int arrSize) {
int left = 0;
int right = arrSize - 1;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
// left左边全都小于arr[left], arr[left]=arr[mid + 1]最大
left = mid + 1;
} else if (arr[mid] > arr[mid + 1]) {
// right右边全都小于arr[right]，arr[right]=arr[mid]最大
right = mid;
}
}
return left;
}
// todo
// 双指针
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
int left = 0, right = numbersSize - 1;
while (left < right) {
if (numbers[left] == target - numbers[right]) {
res[0] = numbers[left];
res[1] = numbers[right];
*returnSize = 2;
return res;
} else if (numbers[left] > target - numbers[right]) {
right--;
} else {
left++;
}
}
return res;
}
// 散列
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
int *hashMap = (int *) calloc(2000001, sizeof(int));
for (int i = 0; i < numbersSize; ++i) {
if ((target - numbers[i]) > 0 && hashMap[target - numbers[i]] == 1) {
res[0] = numbers[i];
res[1] = target - numbers[i];
*returnSize = 2;
return res;
}
hashMap[numbers[i]] = 1;
}
return res;
}
// todo
// 二分+递归
int binarySearch(int *array, int left, int right) {
if (left > right) return -1;
int mid = ((right - left) >> 1) + left;
// 左区间能找到就返回左区间
int leftAns = binarySearch(array, left, mid - 1);
if (leftAns != -1) return leftAns;
// 左区间找不到就检查当前节点
if (array[mid] == mid) return mid;
// 当前节点也不满足就检查右区间
return binarySearch(array, mid + 1, right);
}
int findMagicIndex(int *nums, int numsSize) {
return binarySearch(nums, 0, numsSize - 1);
}
// 双指针
// 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
int left = 0, right = numbersSize - 1;
while (left < right) {
if (numbers[left] == target - numbers[right]) {
res[0] = left;
res[1] = right;
*returnSize = 2;
return res;
} else if (numbers[left] > target - numbers[right]) {
right--;
} else {
left++;
}
}
return res;
}
int binarySearch(int *array, int left, int right, int target) {
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] == target) {
return mid;
} else if (array[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
// 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次
// 在当前节点的右边二分查找
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
for (int i = 0; i < numbersSize; ++i) {
int k = binarySearch(numbers, i + 1, numbersSize - 1, target - numbers[i]);
if (k != -1) {
res[0] = i;
res[1] = k;
*returnSize = 2;
return res;
}
}
return res;
}
int cmp(const void *a, const void *b) {
return (*(int *) a - *(int *) b);
}
// 大于等于（找应该插入的位置，左边界）
int binarySearch1(int *array, int size, int target) {
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (target > array[mid])
left = mid + 1; // left更新之后，left左边必然都小于target
else if (target <= array[mid])
right = mid - 1; // right更新之后，right右边必然都大于等于target
}
// 循环结束时left = right + 1
return left;
}
// 小于等于(右边界)
int binarySearch2(int *array, int size, int target) {
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (target >= array[mid]) // 即使等于left也右移，这样小于等于的就都在left左边了，循环结束时，right就在left-1的位置
left = mid + 1; // left更新之后，left左边必然都小于等于target
else if (target < array[mid])
right = mid - 1; // right更新之后，right右边必然都大于target
}
return right;
}
// 求arr1中与arr2所有元素之差绝对值大于d的元素个数
int findTheDistanceValue(int *arr1, int arr1Size, int *arr2, int arr2Size, int d) {
qsort(arr2, arr2Size, sizeof(int), cmp);
int sum = 0;
for (int i = 0; i < arr1Size; ++i) {
int right = binarySearch1(arr2, arr2Size, arr1[i]);
int left = binarySearch2(arr2, arr2Size, arr1[i]);
printf("%d %d\n", left, right);
if ((left < 0 || abs(arr2[left] - arr1[i]) > d)
&& (right >= arr2Size || abs(arr2[right] - arr1[i]) > d)) {
sum++;
}
}
return sum;
}
int cmp(const void *a, const void *b) {
return *(int *) a - *(int *) b;
}
int binarySearch(int *array, int size, int target) {
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (target == array[mid])
return mid;
else if (target < array[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
int *fairCandySwap(int *aliceSizes, int aliceSizesSize, int *bobSizes, int bobSizesSize, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 2;
// 先把bobSizes排序，再根据aliceSizes[i]在bobSizes中二分查找
qsort(bobSizes, bobSizesSize, sizeof(int), cmp);
int sum1 = 0, sum2 = 0;
for (int i = 0; i < aliceSizesSize; ++i) sum1 += aliceSizes[i];
for (int i = 0; i < bobSizesSize; ++i) sum2 += bobSizes[i];
// sum1给出x，sum2给出y
// sum1-x+y = sum2-y+x
// gap = sum1-sum2 = 2*(x-y)
// y = x - gap/2
int gap = sum1 - sum2;
for (int i = 0; i < aliceSizesSize; ++i) {
int t = binarySearch(bobSizes, bobSizesSize, aliceSizes[i] - gap / 2);
if (t != -1) {
res[0] = aliceSizes[i];
res[1] = bobSizes[t];
return res;
}
}
return res;
}
int cmp(const void *a, const void *b) {
return (*(int *) a) - (*(int *) b);
}
// 左边界
int binarySearch(int *array, int size, int target) {
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
int specialArray(int *nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
for (int i = 0; i <= nums[numsSize - 1]; ++i) {
int index = binarySearch(nums, numsSize, i);
if (numsSize - index == i)
return i;
}
return -1;
}
// 散列
int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
int min = nums1Size > nums2Size ? nums2Size : nums1Size;
int *res = (int *) malloc(sizeof(int) * min);
*returnSize = 0;
int *hashMap = (int *) calloc(1001, sizeof(int));
// 统计出现次数
for (int i = 0; i < nums1Size; ++i) hashMap[nums1[i]]++;
for (int i = 0; i < nums2Size; ++i) {
if (hashMap[nums2[i]] > 0) {
// 表中减一
hashMap[nums2[i]]--;
res[(*returnSize)++] = nums2[i];
}
}
return res;
}
// 左边界
int binarySearch(int *array, int left, int right, int target) {
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
int cmp(const void *a, const void *b) {
return *(int *) a - *(int *) b;
}
// 排序后双指针，第二个指针用二分法定位
int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
int min = nums1Size > nums2Size ? nums2Size : nums1Size;
int *res = (int *) malloc(sizeof(int) * min);
*returnSize = 0;
// 排序
qsort(nums1, nums1Size, sizeof(int), cmp);
qsort(nums2, nums2Size, sizeof(int), cmp);
int j = 0;
for (int i = 0; i < nums1Size && j < nums2Size; ++i) {
int k = binarySearch(nums2, j, nums2Size - 1, nums1[i]);
if (k >= 0 && k < nums2Size && nums1[i] == nums2[k]) {
res[(*returnSize)++] = nums1[i];
// 数组2的j指针同时后移
j = k + 1;
}
}
return res;
}
int binarySearch(char **words, int left, int right, char *s) {
int mid;
while (left <= right) {
// 跳过左右的空字符串
while (left <= right && strcmp(words[left], "") == 0) left++;
while (left <= right && strcmp(words[right], "") == 0) right--;
mid = ((right - left) >> 1) + left;
// 中间的是空字符串，就在两侧找
if (strcmp(words[mid], "") == 0) {
// 找左边
int leftAns = binarySearch(words, left, mid - 1, s);
if (leftAns != -1) return leftAns;
// 找右边
return binarySearch(words, mid + 1, right, s);
}
// 中间不是空字符串
int k = strcmp(words[mid], s);
if (k == 0) {
return mid;
} else if (k > 0) {
right = mid - 1;
} else if (k < 0) {
left = mid + 1;
}
}
return -1;
}
// 二分+递归
int findString(char **words, int wordsSize, char *s) {
return binarySearch(words, 0, wordsSize - 1, s);
}
int findString(char **words, int wordsSize, char *s) {
int left = 0, right = wordsSize - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
int beforeMid = mid;
// 无法二分时，线性探测
while (mid <= right && strcmp(words[mid], "") == 0) {
mid++;
}
if (mid <= right) {
// 没有越界，words[mid]一定不是空字符串
if (strcmp(words[mid], s) == 0) {
return mid;
} else if (strcmp(words[mid], s) > 0) {
right = beforeMid - 1;
} else {
left = mid + 1;
}
} else {
right = beforeMid - 1;
}
}
return -1;
}
int findKthPositive(int *arr, int arrSize, int k) {
int left = 0, right = arrSize - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
// 到arr[mid]为止，包括arr[mid]，缺失的正整数个数
int lossCount = arr[mid] - mid - 1;
// 找左边界
if (lossCount >= k) {
// 代码a，执行这条代码，right右面的必然都满足lossCount >= k
right = mid - 1;
} else {
left = mid + 1;
}
}
// 循环结束一定是left=right+1
// right是刚好lossCount严格小于k的位置，下个位置right+1是lossCount大于等于k的位置（代码a决定的）
if (right >= 0) {
// index = [0,1,2,3,4]
// array = [2,3,4,7,11]
// lossCount = [1,1,1,3,6]
// right = 3, arr[right] = 7, lossCount[right] = 3, lossCount[right+1] = 6
// lossCount[right] < k < lossCount[right+1]，丢失的数一定就在arr[right]到arr[right+1]之间
// 到arr[right]为止，包括arr[right]，缺失的正整数个数为lossCount，从arr[right]往后数（k-lossCount)个数就是答案
return k - (arr[right] - (right) - 1) + arr[right];
}
return k;
}
// 左边界
int binarySearch1(int *array, int size, int target) {
int left = 0, right = size - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
// 右边界
int binarySearch2(int *array, int size, int target) {
int left = 0, right = size - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] <= target)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
int countTarget(int *scores, int scoresSize, int target) {
int left = binarySearch1(scores, scoresSize, target);
int right = binarySearch2(scores, scoresSize, target);
if(left >= scoresSize || scores[left] != target) return 0;
return right - left + 1;
}
// todo
// 含重复元素的增序数组，循环右移后找最小元素
int findMin(int *nums, int numsSize) {
int left = 0;
int right = numsSize - 1;
int mid;
// 规律：最小值下标x，[0,x)值都大于等于末尾元素，[x,array.length-1]都小于等于末尾元素
while (left < right) {
mid = left + (right - left) / 2;
// 和末尾元素比较
if (nums[mid] > nums[right]) {
// [left, mid]都大于numbers[right]，都排除
left = mid + 1;
} else if (nums[mid] < nums[right]) {
// numbers[mid]是[mid,right]上最小的，忽略(mid,right]上的
right = mid;
} else {
// 忽略末尾，新的末尾numbers[right-1]也符合规律
right--;
}
}
return nums[left];
}
// 右边界
int arrangeCoins(int n) {
int left = 1, right = n;
long int mid;
// k行全满，共(1+k)*k/2个元素
while (left <= right) {
mid = ((right - left) >> 1) + left;
long int sum = (1 + mid) * mid >> 1;
if (sum <= n)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
// 小于等于（右边界
bool isPerfectSquare(int num) {
int left = 0;
int right = num;
long int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
long int temp = mid * mid;
if (temp <= num)
left = mid + 1;
else
right = mid - 1;
}
return right * right == num;
}
// 小于等于（右边界
int mySqrt(int x) {
int left = 0;
int right = x;
long int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
long int temp = mid * mid;
if (temp <= x)
left = mid + 1;
else
right = mid - 1;
}
return right;
}