3104 查找一个数是否存在c++解 二分
时间: 2024-10-02 09:00:36 浏览: 24
在C++中,查找一个数是否在一个已排序数组中,通常使用二分查找(Binary Search)算法效率较高。二分查找是一种基于比较的搜索算法,它假设数组已经排好序。以下是基本步骤:
1. 确定数组的起始索引 `low` 和结束索引 `high`。初始时,`low` 为 0,`high` 为数组长度减一。
2. 计算中间索引 `mid`,通常是 `low + (high - low) / 2`。
3. 比较目标值 `target` 和中间元素的值:
- 如果 `target` 等于中间元素,返回中间索引。
- 如果 `target` 小于中间元素,说明目标在左半部分,更新 `high` 为 `mid - 1`。
- 如果 `target` 大于中间元素,说明目标在右半部分,更新 `low` 为 `mid + 1`。
4. 重复上述过程,直到 `low` 大于 `high`,此时可以确定目标不在数组中,返回 `-1` 表示未找到。
这是一个简单的二分查找的伪代码:
```cpp
int binarySearch(int arr[], int target, int n) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1; // 数组中不存在目标值
}
```
阅读全文