#G112. GESP level5 二分算法

GESP level5 二分算法

GESP level5 - 二分算法

  1. 给定序列:1,3,6,9,17,31,39,52,61,79,81,90,96。使用以下代码进行二分查找查找元素82时,需要循环多少次,即最后输出的times值为( )?
int binarySearch(const vector& arr, int target) {
    int left = 0;
    int times = 0;
    int right = arr.size() - 1;
    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(1) }}

  • 2
  • 5
  • 3
  • 4
  1. 二分查找要求被搜索的序列是有序的,否则无法保证正确性。( ) {{ select(2) }}
  • 对
  • 错
  1. 下面C++代码用于有序list的二分查找,有关说法错误的是( )?
int _binarySearch(vector lst, int Low, int High, int Target) {
    if (Low > High)
        return -1;
    int Mid = (Low + High) / 2;
    if (Target == lst[Mid])
        return Mid;
    else if (Target < lst[Mid])
        return _binarySearch(lst, Low, Mid - 1, Target);
    else
        return _binarySearch(lst, Mid + 1, High, Target);
}
int bSearch(vector lst, int Val) {
    return _binarySearch(lst, 0, lst.size(), Val);
}

{{ select(3) }}

  • 代码采用二分法实现有序list的查找
  • 代码采用分治算法实现有序list的查找
  • 代码采用递归方式实现有序list的查找
  • 代码采用动态规划算法实现有序list的查找
  1. 在上题的_binarySearch算法中,如果lst中有N个元素,其时间复杂度是( )? {{ select(4) }}
  • O(N)
  • O(logN)
  • O(NlogN)
  • O(N²)
  1. 下列哪个算法并没有体现分治思想?( ) {{ select(5) }}
  • 二分查找
  • 埃氏筛法
  • 归并排序
  • 快速排序
  1. 阅读下面C++实现的二分查找代码,下列说法中错误的是( )?
int binarySearch(int*arr, int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

{{ select(6) }}

  • 上面代码实现的二分查找,最少只需查找一次即可得到结果
  • 如果调用该函数在列表{2, 3, 4, 10, 12}中查找元素0,则它实际被调用3次
  • 如果调用该函数在列表{2, 3, 4, 10, 12}中查找元素3,则它实际被调用3次
  • 如果调用该函数在列表{2, 3, 4, 10, 12}中查找元素10,则它实际被调用3次
  1. 关于分治算法,以下哪个说法正确?

{{ select(7) }}

  • 分治算法将问题分成子问题,然后分别解决子问题,最后合并结果
  • 归并排序不是分治算法的应用
  • 分治算法通常用于解决小规模问题
  • 分治算法的时间复杂度总是优于O(n log (n))
  1. 根据下述二分查找法,在排好序的数组1,3,6,9,17,31,39,52,61,79中查找数值31,循环while (left <= right)执行的次数为( )?
int binary_search(vector& nums, int target) {
    int left = 0;
    int 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(8) }}

  • 1
  • 2
  • 3
  • 4
  1. 根据下述二分查找法,在排好序的数组1,3,6,9,17,31,39,52,61,79,81,90,96中查找数值82,和82比较的数组元素分别是( )?
int binary_search(vector& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}

{{ select(9) }}

  • 52, 61, 81, 90
  • 52, 79, 90, 81
  • 39, 79, 90, 81
  • 39, 79, 90
  1. 给定一个长度为n的有序数组nums,其中可能包含重复元素。下面的函数返回数组中某个元素target的左边界,若数组中不包含该元素,则返回−1。例如在数组nums = [5,7,7,8,8,10]中查找target=8,函数返回在数组中的左边界的索引为3。则横线上应填写的代码为( )?
int getLeftBoundary(vector& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int middle = left + ((right - left) / 2);
        if (target <= nums[middle]) {
            // 在此处填入代码
        }
        else {
            left = middle + 1;
        }
    }
    return nums[left] == target ? left : -1;
}

{{ select(10) }}

  • right = middle - 1
  • right = middle
  • right = middle + 1
  • 以上都不对
  1. 若用二分法在[1, 100]内猜数,最多需要猜( )次?

{{ select(11) }}

  • 100
  • 10
  • 7
  • 5