折半查找代码
时间: 2023-07-02 16:23:46 浏览: 45
以下是一个示例的折半查找代码:
```
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1; // 如果找不到目标元素,返回 -1
}
```
以上代码使用了迭代方式实现折半查找。其中,`arr` 是要查找的数组,`left` 和 `right` 是数组下标,用于确定当前查找范围。`target` 是要查找的目标元素。
首先,将 `mid` 定义为当前查找范围的中间位置。如果 `arr[mid]` 等于 `target`,则返回 `mid`。如果 `arr[mid]` 小于 `target`,则说明 `target` 在 `mid` 的右侧,将 `left` 更新为 `mid + 1`。如果 `arr[mid]` 大于 `target`,则说明 `target` 在 `mid` 的左侧,将 `right` 更新为 `mid - 1`。如果范围缩小到 `left > right`,则说明找不到目标元素,返回 -1。