二分内容及代码(C语言)
时间: 2023-06-07 18:11:55 浏览: 68
好的,关于二分算法的内容及代码(C语言)如下:
二分算法,又称折半查找,是一种在有序数组中查找某一特定元素的搜索算法。具体思路是,将数组的中间元素与目标元素进行比较,若相等则返回该元素下标,若目标元素较小,则在左半部分继续查找,否则在右半部分查找,直到找到目标元素或确定不存在于数组中。
二分算法的时间复杂度为 O(log n),其优点在于比较次数少,查找速度快。
下面是二分算法的代码实现:
```c
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
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; //目标元素不存在于数组中
}
```
其中,arr[] 表示有序数组,n 表示数组长度,target 表示目标元素。在函数中,利用变量 left 和 right 分别记录数组左右边界,通过不断缩小边界范围实现元素查找。变量 mid 记录左右边界的中间位置,不断与目标元素比较,从而确定目标元素在数组中的位置。若找到目标元素,则返回其下标;否则,返回 -1 表示不存在于数组中。