二分查找（适应于无序数组的一种方法）
二分查找（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。它的原理是从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找成功；如果中间元素小于或大于要查找的元素，则在数组大于或小于中间元素的那一半区域里查找，依次类推，直到找到要查找的元素，或者区域减小到无法再分为止。
例如在一个有序数组{1，2，3，4，5，6，7，8，9，10}中，我们要查找8的位置，就可以先比较其与5的大小关系，发现其大于5，然后就找6与10的中位数8，发现相等，那么8的位置也就找到了，二分查找做法大抵如此。
二分查找的优点是查找速度快，仅需log2n次比较，其中n为数组长度。下面，我将详细介绍如何用C语言实现二分查找算法。 二分查找缺点就是必须要求的是一个有序数组，对于一个无序的数组就需要先处理成有序数组后再进行二分查找。
对于一个无序数组，我们可以通过冒泡排序和二分查找相结合的方法 首先，我们需要创建一个有序数组。这里我们使用一个数组来存储整数，并使用冒泡排序算法对其进行排序。
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array is: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}接下来，我们将实现二分查找算法。
#include <stdio.h>
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; // 如果没有找到目标元素，返回-1
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array is: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
int target = 22;
int result = binarySearch(arr, n, target);
if (result != -1) {
printf("Element %d found at index %d\n", target, result);
} else {
printf("Element %d not found in the array\n", target);
}
return 0;
}上述代码首先对数组进行冒泡排序，然后使用二分查找算法查找有序数组中的目标元素。如果找到目标元素，则输出其索引；否则，输出“Element not found in the array”。
运行上述代码，输出结果如下：
Sorted array is:
11 12 22 25 34 64 90
Element 22 found at index 5通过以上示例，我们可以看到如何使用C语言实现二分查找算法。在实际应用中，二分查找算法可以大大提高查找效率，通过与冒泡排序的结合，也可以让二分查找的方法具有更多的创造力。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-06-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
