二分查找算法
基本思路
二分查找的基本思路如下：
- 找到中间元素：查找过程从数组的中间元素开始，如果中间元素恰好是目标元素，则查找过程结束。
- 比较并缩小范围：如果中间元素不是目标元素，那么将中间元素与目标值进行比较：
- 如果目标值小于中间元素，则说明目标值位于当前搜索范围的左半部分。
- 如果目标值大于中间元素，则说明目标值位于当前搜索范围的右半部分。
- 重复上述过程。不断重复上述过程，每次都将搜索范围缩小一半，直到找到目标值或者发现目标元素不存在。
二分查找的关键在于每次比较后都能排除一半的搜索范围，这使得查找效率非常高，尤其是在大型数组中。
这种算法的时间复杂度为 O(log n)，其中 n 是数组的长度。
代码实现
递归实现
递归实现二分查找
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_LEN(arr) (sizeof(arr)/sizeof(arr[0]))
int bs_recursion(int arr[], int left, int right, int target) {
// 递归的出口
// 如果区间已不存在, 则二分查找结束, 没找到目标元素
if (left > right) {
return -1;
}
int mid = left + (right - left >> 1);
int diff = target - arr[mid];
if (diff < 0)
return bs_recursion(arr, left, mid - 1, target);
if (diff > 0)
return bs_recursion(arr, mid + 1, right, target);
return mid;
}
int binary_search(int arr[], int len, int target) {
bs_recursion(arr, 0, len - 1, target);
}
int main(void) {
int arr[] = { 0,3,5,7,7,9,10, 20,100 };
int len = ARR_LEN(arr);
int target = 7;
int idx = binary_search(arr, len, target);
printf("查找目标元素%d, 它在数组中的索引是%d\n", target, idx);
system("pause");
return 0;
}
循环实现
循环实现二分查找
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_LEN(arr) (sizeof(arr)/sizeof(arr[0]))
int binary_search(int arr[], int len, int target) {
int left = 0, right = len - 1;
while (left <= right) {
int mid = left + (right - left >> 1);
int diff = target - arr[mid];
if (diff < 0)
right = mid - 1;
else if (diff > 0)
left = mid + 1;
else
return mid;
}
return -1;
}
int main(void) {
int arr[] = { 0,3,5,7,7,9,10, 20,100 };
int len = ARR_LEN(arr);
int target = 100;
int idx = binary_search(arr, len, target);
printf("查找目标元素%d, 它在数组中的索引是%d\n", target, idx);
system("pause");
return 0;
}
二分查找变体
查找数组中第一个与目标值相等的元素
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_LEN(arr) (sizeof(arr)/sizeof(arr[0]))
int binary_search_first(int arr[], int len, int target) {
int left = 0, right = len - 1;
while (left <= right) {
int mid = left + (right - left >> 1);
int diff = target - arr[mid];
if (diff < 0)
right = mid - 1;
else if (diff > 0)
left = mid + 1;
else {
if (mid == left || arr[mid - 1] < target)
{
return mid;
}
right = mid - 1;
}
}
return -1;
}
int main(void) {
int arr[] = { 0,3,5,7,7,9,10, 20,100 };
int len = ARR_LEN(arr);
int target = 7;
int idx = binary_search_first(arr, len, target);
printf("查找目标元素%d, 它在数组中的第一个索引是%d\n", target, idx);
system("pause");
return 0;
}
查找数组中最后一个与目标值相等的元素
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_LEN(arr) (sizeof(arr)/sizeof(arr[0]))
int binary_search_last(int arr[], int len, int target) {
int left = 0, right = len - 1;
while (left <= right) {
int mid = left + (right - left >> 1);
int diff = target - arr[mid];
if (diff < 0)
right = mid - 1;
else if (diff > 0)
left = mid + 1;
else {
if (mid == right || arr[mid + 1] > target)
{
return mid;
}
left = mid + 1;
}
}
return -1;
}
int main(void) {
int arr[] = { 0,3,5,7,7,7,9,10, 20,100 };
int len = ARR_LEN(arr);
int target = 7;
int idx = binary_search_last(arr, len, target);
printf("查找目标元素%d, 它在数组中的最后一个索引是%d\n", target, idx);
system("pause");
return 0;
}
查找数组中第一个大于等于目标值的元素
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_LEN(arr) (sizeof(arr)/sizeof(arr[0]))
int binary_search_first_gt(int arr[], int len, int target) {
int left = 0, right = len - 1;
while (left <= right) {
int mid = left + (right - left >> 1);
if (arr[mid] < target)
left = mid + 1;
else {
if (mid == left || arr[mid - 1] < target)
{
return mid;
}
right = mid - 1;
}
}
return -1;
}
int main(void) {
int arr[] = { 0,3,5,7,7,7,9,10, 20,100 };
int len = ARR_LEN(arr);
int target = 7;
int idx = binary_search_first_gt(arr, len, target);
printf("查找数组中第一个大于等于目标值%d的元素, 它是%d, 在索引%d\n", target,arr[idx], idx);
system("pause");
return 0;
}
查找数组中最后一个小于等于目标值的元素
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_LEN(arr) (sizeof(arr)/sizeof(arr[0]))
int binary_search_last_lt(int arr[], int len, int target) {
int left = 0, right = len - 1;
while (left <= right) {
int mid = left + (right - left >> 1);
if (arr[mid] > target)
right = mid - 1;
else {
if (mid == right || arr[mid + 1] > target)
{
return mid;
}
left = mid + 1;
}
}
return -1;
}
int main(void) {
int arr[] = { 0,3,5,7,7,7,9,10, 20,100 };
int len = ARR_LEN(arr);
int target = 8;
int idx = binary_search_last_lt(arr, len, target);
printf("查找数组中最后一个小于等于目标值%d的元素, 它是%d, 在索引%d\n", target, arr[idx], idx);
system("pause");
return 0;
}
典型应用
IP归属地查询
改进插入排序
二分查找是可以改进插入排序的，其核心思路是，每一轮插入排序都会有一张"新抓手牌"，而"旧手牌"是一个已经有序的数组。传统的做法是：
让"新手牌"逐一和"旧手牌"有序数组中的元素逐一比较，然后确定"新手牌"的插入位置，向后移动元素，将"新手牌"插入。如下图所示：
当数据量比较大时，"旧手牌"比较多，有序数组很长时，可以考虑用二分查找，替代逐一比较查找待插入位置。那么这个二分查找是在找什么呢？
当然是查找最后一个小于等于"新手牌"值的元素，这样就可以直接将它后面的所有元素后移一位，然后再它后面直接插入"新手牌"。
当然，这种改进在实际应用中并不常见：
- 插入排序本身就应用于小数据集，大数据集情况下大多不会选择插入排序。
- 既然是应用于小数据集，数组本身较短，用二分查找的意义就不大了。对效率的提升不明显，而且还增加了复杂性。
使用二分查找改进的插入排序
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_LEN(arr) (sizeof(arr)/sizeof(arr[0]))
int binary_sort(int arr[], int left,int right, int target) {
while (left <= right) {
int mid = left + (right - left >> 1);
if (arr[mid]>target)
{
right = mid - 1;
}
else
{
if (mid == right||arr[mid+1]>target)
{
return mid;
}
left = mid + 1;
}
}
return -1;
}
void binary_insertion_sort(int arr[], int len) {
for (int i = 1; i < len; i++)
{
int value = arr[i];
// 使用二分查找找到应插入的位置
// idx(不包括)后面的所有元素都有后移一位，idx + 1是value要插入的位置
int idx = binary_sort(arr, 0,i-1, value);
int j = i - 1; // j在这里赋值为有序数组的最后一个元素
while (j > idx) { // 有序数组中的元素只要下标大于idx就后移 也就是不包括idx，但idx后面的所有元素都要后移
arr[j + 1] = arr[j];
j--;
} // j == idx;
arr[j + 1] = value;
}
}
int main(void) {
int arr[] = { 9, 5, 2, 7, 1, 3, 4, 0, 8, 6 };
int len = ARR_LEN(arr);
binary_insertion_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
system("pause");
return 0;
}