二分法是一种经典的搜索算法,常用于在有序数组中快速查找目标值。它的核心思想是通过不断缩小搜索范围来提高效率,时间复杂度仅为O(log n)!✨
假设我们有一个升序排列的整数数组 `[1, 3, 5, 7, 9]`,现在需要查找数字 `7` 是否存在。首先定义左右边界 `left = 0` 和 `right = length - 1`。接着计算中间索引 `mid = (left + right) / 2`,比较 `array[mid]` 和目标值:
- 如果 `array[mid] == target`,则找到目标值;
- 如果 `array[mid] > target`,则在左半部分继续查找;
- 如果 `array[mid] < target`,则在右半部分继续查找。
重复上述步骤直到找到目标值或搜索范围为空为止。以下是用C语言实现的代码片段👇:
```c
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; // 未找到目标值
}
```
二分法不仅高效,还广泛应用于实际问题中,比如数据排序、文件查找等。掌握它,你就是算法领域的“小达人”啦!🎉
算法 C语言 编程学习 二分法