二分法(又称折半查找法)是一种在有序数组中查找目标值的高效算法。
以下是使用C语言实现的二分法查找函数:
#include <stdio.h>
int binary_search(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
int mid;
while (left <= right) {
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
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 11;
int result = binary_search(arr, n, target);
if (result != -1) {
printf("元素在数组中的索引为 %d/n", result);
} else {
printf("元素在数组中不存在/n");
}
return 0;
}
在这个例子中,binary_search
函数接收一个有序整数数组、数组长度以及目标值作为参数。
函数通过不断将搜索范围缩小一半来寻找目标值,直到找到目标值或搜索范围为空。
如果找到目标值,则返回其在数组中的索引;否则返回-1。
main
函数中定义了一个有序整数数组 arr
和一个目标值 target
,调用 binary_search
函数来查找目标值在数组中的位置,并输出结果。