一个有序数组,用中间法。
时间: 2024-03-05 10:50:57 浏览: 12
有序数组的中间查找法(也称为二分查找法)是一种常见的查找算法,可以在 $O(\log n)$ 的时间复杂度内查找一个有序数组中的某个元素。具体步骤如下:
1. 定义数组的左边界 `left` 和右边界 `right`,并计算数组的中间下标 `mid`,即 `mid = (left + right) / 2`。
2. 将中间元素 `arr[mid]` 与目标元素 `target` 进行比较。
- 如果 `arr[mid]` 等于 `target`,则查找成功,返回 `mid`。
- 如果 `arr[mid]` 大于 `target`,则说明目标元素可能在数组的左半部分,将右边界 `right` 更新为 `mid - 1`。
- 如果 `arr[mid]` 小于 `target`,则说明目标元素可能在数组的右半部分,将左边界 `left` 更新为 `mid + 1`。
3. 重复步骤 1 和 2,直到左边界 `left` 大于右边界 `right`,此时表明目标元素不在数组中,返回 -1。
以下是一个使用中间法查找有序数组的例子:
```c
#include <stdio.h>
int binarySearch(int arr[], int n, int target);
int main()
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int index = binarySearch(arr, n, target);
if (index == -1) {
printf("Element not found.\n");
} else {
printf("Element found at index %d.\n", index);
}
return 0;
}
int binarySearch(int arr[], int n, int target)
{
int left = 0, right = n - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
```
在这个例子中,我们定义了一个有序数组 `arr`,并使用 `binarySearch()` 函数在其中查找目标元素 `target`。该函数接受三个参数:要搜索的数组 `arr`、数组的大小 `n` 和目标元素 `target`。在函数中,我们使用 `left` 和 `right` 分别表示数组的左边界和右边界,然后使用一个 while 循环来不断缩小搜索范围。在每次循环中,我们都计算中间下标 `mid`,并将中间元素 `arr[mid]` 与目标元素 `target` 进行比较,根据比较结果更新搜索范围的左边界或右边界。最终,如果找到目标元素,则返回其下标,否则返回 -1。