C语言二分查找代码如下：，，``
c，#include ，，int binary_search(int arr[], int size, int target) {， int left = 0;， int right = size - 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;，}，，int main() {， int arr[] = {1, 3, 5, 7, 9};， int size = sizeof(arr) / sizeof(arr[0]);， int target = 5;，， int result = binary_search(arr, size, target);， printf("元素 %d 在数组中的位置是： %d，", target, result);，， return 0;，}， ``二分查找算法简介
二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法，搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较，如果在某一步骤数组为空，则代表找不到，这种搜索算法每一次比较都使搜索范围缩小一半。
C语言实现二分查找的代码
include <stdio.h>
int binary_search(int arr[], int size, int target) {
int left = 0;
int right = size 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;
}
使用示例
include <stdio.h>
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 11;
int result = binary_search(arr, size, target);
if (result != -1) {
printf("找到目标值 %d 在数组中的位置是： %d
", target, result);
} else {
printf("在数组中未找到目标值 %d
", target);
}
return 0;
}
相关问题与解答
1、为什么二分查找的时间复杂度是O(logn)?
答：因为每次循环后，搜索范围都会缩小一半，所以时间复杂度为对数级别。
2、如果数组中有重复元素，二分查找还能正常工作吗？
答：不能，当有重复元素时，需要修改算法来处理这种情况，一种简单的方法是在比较时同时检查两个相邻的元素是否相等，如果相等且要查找的元素比它们都大或小，则继续在相应的一侧查找；否则返回-1表示未找到。
原创文章，作者：K-seo，如若转载，请注明出处：https://www.kdun.cn/ask/194308.html
微信扫一扫 