数据结构与算法存入在 a[n+1]数组中的 n 个有序元素进行二分查找的程序。
时间: 2024-02-15 10:06:03 浏览: 29
好的,这个问题很简单。以下是使用二分查找在有序数组 a[n+1] 中查找元素 x 的程序:
```
int binarySearch(int a[], int n, int x) {
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (a[mid] == x) {
return mid;
} else if (a[mid] < x) {
left = mid + 1;
} else {
right = mid;
}
}
return -1; // 表示未找到
}
```
解释一下上面的代码:
- 初始化左右边界,左边界为 0,右边界为 n,表示初始时整个数组都是待查找区间。
- 进入循环,判断左右边界是否相遇。如果相遇,表示已经找完了整个待查找区间,但是还没有找到目标元素,返回 -1 表示未找到。
- 计算中间位置 mid,并用 a[mid] 与目标元素 x 进行比较。
- 如果相等,表示已经找到目标元素,返回 mid。
- 如果 a[mid] 小于 x,表示目标元素在右半边,调整左边界 left 为 mid + 1。
- 如果 a[mid] 大于 x,表示目标元素在左半边,调整右边界 right 为 mid。
- 如果循环体内没有找到目标元素,会继续进行下一轮循环,直到找到目标元素或者整个待查找区间已经被缩小到只有一个元素为止。
这就是二分查找的基本思路,它的时间复杂度是 O(log n)。