#G112. GESP level5 二分算法
GESP level5 二分算法
GESP level5 - 二分算法
- 给定序列: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
- 二分查找要求被搜索的序列是有序的,否则无法保证正确性。( ) {{ select(2) }}
- 对
- 错
- 下面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的查找
- 在上题的_binarySearch算法中,如果lst中有N个元素,其时间复杂度是( )? {{ select(4) }}
- O(N)
- O(logN)
- O(NlogN)
- O(N²)
- 下列哪个算法并没有体现分治思想?( ) {{ select(5) }}
- 二分查找
- 埃氏筛法
- 归并排序
- 快速排序
- 阅读下面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次
- 关于分治算法,以下哪个说法正确?
{{ select(7) }}
- 分治算法将问题分成子问题,然后分别解决子问题,最后合并结果
- 归并排序不是分治算法的应用
- 分治算法通常用于解决小规模问题
- 分治算法的时间复杂度总是优于O(n log (n))
- 根据下述二分查找法,在排好序的数组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,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
- 给定一个长度为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, 100]内猜数,最多需要猜( )次?
{{ select(11) }}
- 100
- 10
- 7
- 5