二分查找（共 10 题）

单选题

1. 在升序数组中查找第一个大于等于 x 的位置，下面循环中横线应填（ ）。

   int lowerBound(const vector<int>& a, int x) {
       int l = 0, r = a.size();
       while (l < r) {
           int mid = l + (r - l) / 2;
           if (a[mid] > x) __________________;
           else l = mid + 1;
       }
       return l;
   }
   

   {{ select(1) }}

• r = mid
• r = mid - 1
• r = mid + 1
• 不填

2. 给定一个长度为 n 的有序数组 nums，其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。若 target 不存在，则返回 -1。该算法的时间复杂度是（ ）。

   int binarySearch(vector<int> &nums, int target, int left, int right) {
       if (left > right) return -1;
       int middle = left + (right - left) / 2;
       if (nums[middle] == target) return middle;
       else if (nums[middle] < target) 
           return binarySearch(nums, target, middle+1, right);
       else
           return binarySearch(nums, target, left, middle-1);
   }
   

   {{ select(2) }}

• O(N)
• O(log N)
• O(N log N)
• O(N²)

3. 给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使用以下代码进行二分查找查找元素 82 时，需要循环多少次，即最后输出的 times 值为（ ）。

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

   {{ select(3) }}

• 2
• 5
• 3
• 4

4. 在有序数组中进行二分查找，查找 82 的数组是：1,3,6,9,17,31,39,52,61,79,81,90,96。比较的元素依次是（ ）。
   {{ select(4) }}

• 52,79,90,81
• 52,61,81,90
• 39,79,90,81
• 52,81,90

5. 若用二分法在 [1,100] 内猜数，最多需要猜（ ）次。
   {{ select(5) }}

• 100
• 10
• 7
• 5

6. 下面代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，则横线上能填写的最佳代码是（ ）。

   int binarySearch(int arr[], int left, int right, int target) {
       while (left <= right) {
           __________________
           if (arr[mid] == target) return mid;
           else if (arr[mid] < target) left = mid + 1;
           else right = mid - 1;
       }
       return -1;
   }
   

   {{ select(6) }}

• int mid = left + (right - left) / 2;
• int mid = left;
• int mid = (left + right) / 2;
• int mid = right;

7. 下面代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素，返回 arr.size()。以下说法正确的是（ ）。

   int lower_bound(vector<int>& arr, int x) {
       int l = 0, r = arr.size();
       while (l < r) {
           int mid = l + (r - l) / 2;
           if (arr[mid] >= x) r = mid;
           else l = mid + 1;
       }
       return l;
   }
   

   {{ select(7) }}

• 上述代码逻辑正确
• 上述代码逻辑错误，while 循环条件应该用 l <= r
• 上述代码逻辑错误，mid 计算错误
• 上述代码逻辑错误，边界条件不对

8. 小杨要把一根长度为 L 的木头切成 K 段，使得每段长度小于等于 x。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 x（x 为正整数），则横线处应填写（ ）。

   bool check(int L, int K, int x) {
       int cuts = (L - 1) / x;
       return cuts <= K;
   }
   int binary_cut(int L, int K) {
       int l = 1, r = L;
       while (l < r) {
           int mid = l + (r - l) / 2;
           __________________
       }
       return l;
   }
   

   {{ select(8) }}

• if (check(L, K, mid)) r = mid; else l = mid + 1;
• if (check(L, K, mid)) r = mid + 1; else l = mid + 1;
• if (check(L, K, mid)) r = mid + 1; else l = mid - 1;
• if (check(L, K, mid)) r = mid + 1; else l = mid;

9. 在升序数组中查找第一个大于等于 x 的位置，下面循环中横线应填（ ）。

   int lowerBound(const vector<int>& a, int x) {
       int l = 0, r = a.size();
       while (l < r) {
           int mid = l + (r - l) / 2;
           if (a[mid] > x) r = mid;
           else l = mid + 1;
       }
       return l;
   }
   

   {{ select(9) }}

• r = mid
• r = mid - 1
• r = mid + 1
• 不填

10. 根据下述二分查找法，在排好序的数组 1，3，6，9，17，31，39，52，61，79 中查找数值 31，循环 while (left <= right) 执行的次数为（ ）。

    int binary_search(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;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
    

    {{ select(10) }}

• 1
• 2
• 3
• 4

判断题

11. 若数组 a 已按升序排列，则下面代码可以正确实现“在 a 中查找第一个大于等于 x 的元素的位置”。

    int lowerBound(vector<int>& a, int x) {
        int l = 0, r = a.size();
        while (l < r) {
            int mid = (l+r)/2;
            if (a[mid] >= x) r = mid;
            else l = mid+1;
        }
        return l;
    }
    

    {{ select(11) }}

• 正确
• 错误

12. 二分查找要求被搜索的序列是有序的，否则无法保证正确性。
    {{ select(12) }}

• 正确
• 错误

13. 二分查找仅适用于数组而不适合链表，因为二分查找需要跳跃式访问元素，链表中执行跳跃式访问的效率低。
    {{ select(13) }}

• 正确
• 错误

14. 对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进行二分查找，成功查找元素 19 的比较次数是 2。
    {{ select(14) }}

• 正确
• 错误

15. 二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。
    {{ select(15) }}

• 正确
• 错误