编程中折半法怎么用

折半查找法（也称为二分查找法）是一种在有序数组中查找某一特定元素的搜索算法。其基本思想是每次将查找范围缩小一半，直到找到目标元素或范围缩小为零。以下是折半查找法的基本步骤和代码实现：

基本步骤

初始化：

设定两个指针，`low` 和 `high`，分别指向数组的起始位置和结束位置。

计算中间位置：

使用 `mid = （low + high） / 2` 计算中间位置。

比较：

将目标值与中间位置的元素进行比较：

如果目标值等于中间位置的元素，查找成功，返回中间位置的下标。

如果目标值小于中间位置的元素，更新 `high = mid - 1`，继续在左半部分查找。

如果目标值大于中间位置的元素，更新 `low = mid + 1`，继续在右半部分查找。

重复步骤2和3 ，直到找到目标值或 `low` 超过 `high`（即查找范围为空）。

代码实现

```cpp

include

using namespace std；

int binarySearch（int arr[], int len, int key） {

int low = 0； // 定义初始最小下标

int high = len - 1； // 定义初始最大下标

int mid； // 定义中间下标

while （low <= high） {

mid = （high + low） / 2； // 计算中间下标

if （arr[mid] == key） {

return mid； // 找到目标值，返回中间下标

} else if （arr[mid] < key） {

low = mid + 1； // 目标值在右半部分

} else {

high = mid - 1； // 目标值在左半部分

}

}

return -1； // 没有找到目标值，返回-1

}

int main（） {

int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}；

int key = 7；

int result = binarySearch（arr, 11, key）；

if （result != -1） {

cout << "Element found at index: " << result << endl；

} else {

cout << "Element not found in the array." << endl；

}

return 0；

}

```

注意事项

有序数组：

折半查找法要求数组必须是有序的，无论是升序还是降序。

初始边界：

`low` 初始化为0，`high` 初始化为数组长度减1。

中间值计算：

使用 `（low + high） / 2` 计算中间下标，注意整数除法可能向下取整。

循环条件：

循环条件是 `low <= high`，确保在缩小范围时不会漏掉目标值。

通过以上步骤和代码实现，你可以有效地使用折半查找法在有序数组中查找目标值。