二分法（相关题目）

#include<stdio.h>
int n, m, q, a[1000005];
int find(int x)
{
	int l = 1, r = n;
	while (l < r)
	{
		int mid = l + (r - l) / 2;
		if (a[mid] >= x)
			r = mid;
		else
			l = mid + 1;
	}
	if (a[l] == x) return l;
	else return -1;
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &q);
		int ans = find(q);
		printf("%d ", ans);
	}
	return 0;
}

#include <stdio.h>

int check(int arr[], int n, int initialHealth) {
    int currentHealth = initialHealth;
    
    for (int i = 0; i < n; ++i) {
        if (arr[i] < 0) {
            // 关卡是战斗，扣除血量
            currentHealth += arr[i];
        } else {
            // 关卡是营地，增加血量
            currentHealth += arr[i];
        }

        // 如果任意时刻血量小于等于0，则返回0表示初始血量不足
        if (currentHealth <= 0) {
            return 0;
        }
    }

    // 返回1表示初始血量足够
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);

    int arr[n];
    int low = 1, high = 1;  // 初始血量的范围

    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
        // 更新初始血量的范围
        if (arr[i] < 0) {
            high -= arr[i];
        } else {
            high += arr[i];
        }
    }

    int result = 0;

    // 二分法查找最小的初始血量
    while (low <= high) {
        int mid = (low + high) / 2;

        // 如果初始血量足够，继续搜索左半部分
        if (check(arr, n, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            // 初始血量不足，搜索右半部分
            low = mid + 1;
        }
    }

    printf("%d\n", result);

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
// 比较函数用于排序
int compare(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

// 二分查找
int binary_search(const int* arr, int size, int target)
{
    int left = 0, right = size - 1;
    int count = 0;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
        {
            count++;
            // 继续查找可能的相同值
            int next = mid + 1;
            while (next < size && arr[next] == target)
            {
                count++;
                next++;
            }
            // 向左查找可能的相同值
            int prev = mid - 1;
            while (prev >= 0 && arr[prev] == target) 
            {
                count++;
                prev--;
            }
            return count;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return count;
}

int main()
{
    int N, C;
    scanf("%d %d", &N, &C);
    int* arr = (int*)malloc(N * sizeof(int));
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &arr[i]);
    }

    qsort(arr, N, sizeof(int), compare);  // 对数列进行排序

    int count = 0;
    for (int i = 0; i < N; i++) 
    {
        int target = arr[i] - C;
        count += binary_search(arr, N, target);
    }

    printf("%d\n", count);

    free(arr);
    return 0;
}