给定一个n个元素有序的(升序)整型数组nums和一个目标值target,使用折半查找目标值,如果目标值存在返回下标,否则返回-1。
时间: 2024-11-09 11:30:06 浏览: 28
在C语言中,你可以使用二分查找(Binary Search)算法来解决这个问题。二分查找是一种非常高效的数据搜索算法,它适用于已经排好序的数组。以下是简单的步骤和伪代码描述:
1. 初始化两个指针,`low`表示数组的起始位置(0),`high`表示数组的结束位置(n-1)。
2. 计算中间索引 `mid` = (`low` + `high`) / 2。
3. 检查中间元素 `nums[mid]` 是否等于目标值 `target`:
a. 如果相等,返回 `mid`。
b. 如果 `nums[mid]` 大于目标值,则在左半部分(即 `low` 到 `mid-1`)继续查找。
c. 如果 `nums[mid]` 小于目标值,则在右半部分(即 `mid+1` 到 `high`)继续查找。
4. 如果遍历完整个数组都没有找到目标值,返回 -1。
这是一个基本的二分查找函数的实现示例:
```c
int binary_search(int nums[], int target, int n) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // 目标值不存在
}
```
阅读全文