运用二分查找在序列{1,2,3,……,n}中找到k需要循环多少次? Input 输入多组数据, 每组输入两个整数n和k,占一行(0<= k <= n)。n为32位整数 Output 对每组输入,输出在序列{1,2,3,……,n}中找到k的循环次数。 Sample Input 5 2 5 1 10 3
时间: 2024-03-13 07:47:28 浏览: 15
这是一个经典的二分查找问题。在一个长度为n的有序序列中查找一个数k,最多需要进行log2(n)次比较即可找到。
以下是Python的代码实现:
```python
import math
while True:
try:
n, k = map(int, input().split())
left, right = 1, n
count = 0
while left <= right:
mid = (left + right) // 2
if mid == k:
break
elif mid < k:
left = mid + 1
else:
right = mid - 1
count += 1
print(count)
except:
break
```
输入多组数据,每次读入一行并以空格分隔成两个整数n和k。然后用二分查找的方法在序列{1, 2, 3, ..., n}中查找k,并记录循环次数。输出循环次数即可。程序会一直循环读入数据,直到遇到EOF。
相关问题
C语言运用二分查找在序列{1,2,3,……,n}中找到k需要循环多少次? Input 输入多组数据, 每组输入两个整数n和k,占一行(0<= k <= n)。n为32位整数 Output 对每组输入,输出在序列{1,2,3,……,n}中找到k的循环次数。 Sample Input 5 2 5 1 10 3
C语言的代码实现如下:
```c
#include <stdio.h>
int main()
{
int n, k;
while (scanf("%d%d", &n, &k) != EOF) {
int left = 1, right = n;
int count = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (mid == k) {
break;
} else if (mid < k) {
left = mid + 1;
} else {
right = mid - 1;
}
count++;
}
printf("%d\n", count);
}
return 0;
}
```
C语言也可以使用循环读入多组数据,每组输入两个整数n和k。然后用二分查找的方法在序列{1, 2, 3, ..., n}中查找k,并记录循环次数。输出循环次数即可。程序会一直循环读入数据,直到遇到EOF。
c++ 运用二分查找在序列{1,2,3,……,n}中找到k需要循环多少次? Input 输入多组数据, 每组输入两个整数n和k,占一行(0<= k <= n)。n为32位整数 Output 对每组输入,输出在序列{1,2,3,……,n}中找到k的循环次数。 Sample Input 5 2 5 1 10 3
C++的代码实现如下:
```c++
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int n, k;
while (cin >> n >> k) {
int left = 1, right = n;
int count = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (mid == k) {
break;
} else if (mid < k) {
left = mid + 1;
} else {
right = mid - 1;
}
count++;
}
cout << count << endl;
}
return 0;
}
```
与Python类似,C++也可以使用循环读入多组数据,每组输入两个整数n和k。然后用二分查找的方法在序列{1, 2, 3, ..., n}中查找k,并记录循环次数。输出循环次数即可。程序会一直循环读入数据,直到遇到EOF。