6-1 二分查找 分数 20
时间: 2023-07-19 16:28:52 浏览: 113
您好,二分查找是一种常见的查找算法,在有序数组中查找指定元素的位置。算法的基本思想是将数组分成两半,确定待查找元素可能在哪一半,然后继续将该部分数组分成两半,直到找到该元素或者确定该元素不在数组中。下面是一个简单的二分查找的实现示例:
```c++
int binarySearch(int arr[], int n, int target) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
```
其中,arr是有序数组,n是数组长度,target是待查找的元素。函数返回该元素在数组中的位置,如果不存在,则返回-1。
相关问题
7-4 查找最接近的元素 分数 20 作者 zhu weihua 单位 新余学院 在一个非降序列中,
给定一个整数x,请设计一个高效算法,查找序列中最接近x的数。 如果有多个最接近x的数,则返回序号最小的数的下标(从0开始)。 如果序列中没有元素,则返回-1。
函数头部: int find(int* a, int n, int x);
输入参数:
a:非降序列,数组a中存放n个整数(0<=n<=10^6,-10^9<=a[i]<=10^9)。
n:非降序列中元素的个数。
x:需要查找的整数(-10^9<=x<=10^9)。
输出参数:
函数返回值:序列中最接近x的数的下标。
输入样例:
a: 1 2 3 4 5 6
n: 6
x: 3
输出样例:
2
算法1
(二分查找) $O(logn)$
由于是非降序列,可以使用二分查找法。
首先特判序列为空的情况,如果序列为空,则返回-1。
如果序列不为空,则在序列中进行二分查找,找到最接近x的数。具体的方法是设两个指针left和right,分别指向序列的第一个元素和最后一个元素。然后不断将区间缩小,直到left和right相邻为止。最后判断left和right哪一个更接近x即可。
R6-3 二分查找 分数 17 作者 陈越 单位 浙江大学 本题要求实现二分查找算法。 函数接口定义: Position BinarySearch( List L, ElementType X ); 其中List结构定义如下: typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; L是用户传入的一个线性表,其中ElementType元素可以通过>、==、<进行比较,并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置,即数组下标(注意:元素从下标1开始存储)。找到则返回下标,否则返回一个特殊的失败标记NotFound。 裁判测试程序样例: #include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 #define NotFound 0 typedef int ElementType; typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; List ReadInput(); /* 裁判实现,细节不表。元素从下标1开始存储 */ Position BinarySearch( List L, ElementType X ); int main() { List L; ElementType X; Position P; L = ReadInput(); scanf("%d", &X); P = BinarySearch( L, X ); printf("%d\n", P); return 0; } /* 你的代码将被嵌在这里 */ 输入样例1: 5 12 31 55 89 101 31 输出样例1: 2 输入样例2: 3 26 78 233 31 输出样例2: 0
下面是二分查找的实现代码:
```
Position BinarySearch(List L, ElementType X)
{
Position left = 1; // 左边界
Position right = L->Last; // 右边界
while (left <= right) {
Position mid = (left + right) / 2; // 中间位置
if (L->Data[mid] == X) { // 找到了
return mid;
} else if (L->Data[mid] > X) { // 往左边找
right = mid - 1;
} else { // 往右边找
left = mid + 1;
}
}
// 没找到
return NotFound;
}
```
具体思路是:首先设置左边界为1,右边界为L的最后一个元素的位置;然后在每一次循环中,取左右边界的平均值作为中间位置mid,并将L->Data[mid]和X进行比较,如果相等,则找到了,返回mid;如果L->Data[mid]比X大,则说明要在mid的左边继续查找,此时将右边界right更新为mid-1;否则说明要在mid的右边继续查找,此时将左边界left更新为mid+1。如果最终没有找到,返回NotFound。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)