普及组二分查找专题训练

题目1：基本二分查找（简单）

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target;
    cin >> target;
    
    int result = binarySearch(arr, target);
    
    if (result != -1) {
        cout << "元素 " << target << " 在位置 " << result << endl;
    } else {
        cout << "元素 " << target << " 不存在" << endl;
    }
    
    return 0;
}

判断题

1. 二分查找要求数组必须是有序的。 ( )
2. 如果目标元素在数组中存在多个，该程序会返回第一个出现的位置。 ( )
3. 当数组为空时，程序会正常执行并返回-1。 ( )

选择题 4. 在包含10个元素的有序数组中，二分查找最多需要比较（ ）次。 A. 3 B. 4 C. 5 D. 10

5. 如果输入target=8，程序的输出是（ ）。 A. 元素8在位置3 B. 元素8在位置4 C. 元素8不存在 D. 程序出错

题目2：查找第一个大于等于目标值的位置（中等）

#include <iostream>
#include <vector>
using namespace std;

int firstGreaterOrEqual(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = arr.size();
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] >= target) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

int main() {
    vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int target;
    cin >> target;
    
    int pos = firstGreaterOrEqual(arr, target);
    
    if (pos < arr.size()) {
        cout << "第一个大于等于" << target << "的元素是" << arr[pos] << "，位置" << pos << endl;
    } else {
        cout << "所有元素都小于" << target << endl;
    }
    
    return 0;
}

判断题

1. 这个算法可以用来实现C++标准库中的lower_bound函数。 ( )
2. 如果目标值在数组中存在，该函数会返回目标值的第一个出现位置。 ( )
3. 当target=15时，函数返回值为7。 ( )

选择题 4. 如果输入target=5，程序的输出是（ ）。 A. 第一个大于等于5的元素是6，位置2 B. 第一个大于等于5的元素是6，位置3 C. 第一个大于等于5的元素是8，位置3 D. 所有元素都小于5

5. 这个算法的时间复杂度是（ ）。 A. O(1) B. O(log n) C. O(n) D. O(n²)

题目3：在旋转有序数组中查找目标值（中等偏难）

#include <iostream>
#include <vector>
using namespace std;

int searchInRotatedArray(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        }
        
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

int main() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    int target;
    cin >> target;
    
    int result = searchInRotatedArray(nums, target);
    
    if (result != -1) {
        cout << "元素 " << target << " 在位置 " << result << endl;
    } else {
        cout << "元素 " << target << " 不存在" << endl;
    }
    
    return 0;
}

判断题

1. 这个算法只能处理旋转一次的有序数组。 ( )
2. 如果数组没有旋转，这个算法会退化为普通的二分查找。 ( )
3. 对于输入target=0，程序会返回位置4。 ( )

选择题 4. 如果输入target=3，程序的输出是（ ）。 A. 元素3在位置3 B. 元素3在位置5 C. 元素3不存在 D. 程序出错

5. 这个算法的核心思想是（ ）。 A. 先找到旋转点，再进行二分查找 B. 每次判断哪部分是有序的，然后在有序部分进行二分查找 C. 将数组恢复为有序数组，再进行二分查找 D. 使用线性查找

题目4：二分答案-求平方根（难）

#include <iostream>
using namespace std;

int mySqrt(int x) {
    if (x == 0 || x == 1) return x;
    
    int left = 1, right = x;
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (mid <= x / mid) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    int x;
    cin >> x;
    
    int result = mySqrt(x);
    cout << x << "的平方根是" << result << endl;
    
    return 0;
}

判断题

1. 这个算法使用二分查找来逼近平方根的整数部分。 ( )
2. 对于x=8，函数返回2。 ( )
3. 使用mid <= x / mid而不是mid * mid <= x是为了避免整数溢出。 ( )

选择题 4. 如果输入x=15，程序的输出是（ ）。 A. 2 B. 3 C. 4 D. 5

5. 这个算法的时间复杂度是（ ）。 A. O(1) B. O(log x) C. O(√x) D. O(x)

题目5：二分答案-最大值最小化问题（最难）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canSplit(vector<int>& nums, int k, int maxSum) {
    int count = 1;
    int currentSum = 0;
    
    for (int num : nums) {
        if (currentSum + num > maxSum) {
            count++;
            currentSum = num;
            if (count > k) return false;
        } else {
            currentSum += num;
        }
    }
    
    return true;
}

int splitArray(vector<int>& nums, int k) {
    int left = *max_element(nums.begin(), nums.end());
    int right = 0;
    for (int num : nums) right += num;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (canSplit(nums, k, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    vector<int> nums = {7, 2, 5, 10, 8};
    int k;
    cin >> k;
    
    int result = splitArray(nums, k);
    cout << "将数组分割成" << k << "段，最小化最大子数组和为：" << result << endl;
    
    return 0;
}

判断题

1. 这个算法使用二分答案来解决问题。 ( )
2. 当k=1时，函数返回数组所有元素之和。 ( )
3. canSplit函数使用贪心策略来判断是否可行。 ( )

选择题 4. 如果输入k=2，程序的输出是（ ）。 A. 14 B. 18 C. 21 D. 32

5. 这个算法解决的是（ ）问题。 A. 最小化最大值 B. 最大化最小值 C. 寻找中位数 D. 计算平均值