🔥前言
二分查找又称为折半查找，是分治算法基础上设计出来的查找算法。
二分查找算法仅适用于有序序列，它只能用升序序列或者降序序列中查找目标元素。
🔥算法描述
二分查找的核心思想：不断地缩小搜索的区域，降低查找目标元素的难度。
前提：有已排序的数组arr。
定义左边界（Left），定义右边界（Right），确定搜索范围，循环执行二分查找.
获得中间下标 Middle = (Left + Right) / 2。
中间下标的值，arr[Middle] 与待搜索的值 t 进行比较。
arr[Middle] == t 表示知道了，返回中间下标
arr[Middle] > t 中间值右侧的其他元素都大于t，不需要比较，中间下标左边去找，Middle - 1 设置右边界，重新查找。
arr[Middle] < t 中间值左侧的其他元素都小于t，不需要比较，中间下标右边去找，Middle + 1 设置左边界，重新查找。
当 Left > Right ,表示没有找到，循环结束。
🔥算法实现
void binarysearch(int arr[], int Length, int t) // 数组、数组长度和要查找的数 { int find = -1;//标记 int Left = 0; // 左边界 int Right = Length - 1; // 右边界 int Middle = 0; // 中间值 while (Left <= Right) // Left > Right ,表示没有找到，循环结束。 { Middle = (Left + Right) / 2; if (arr[Middle] == t) // 找到了 { find = 1; break; } else if (arr[Middle] > t) // 右侧都大于t Right = Middle - 1; else // 左侧都小于t Left = Middle + 1; } if (1 == find) printf("找到了，下标为：%d\n", Middle); else printf("没有找到\n"); }
🔥测试代码
int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; int Length = sizeof(arr) / sizeof(arr[0]); // 计算数组长度 int t = 0; scanf("%d", &t); binarysearch(arr, Length, t); return 0; }
🔥解决溢出问题
当Left 和 Right 都较大时，Left + Right 有可能会超出整数的范围，造成计算错误，可以使用以下解决方法。
Middle = Left + (Right - Left) / 2;
🔥代码
#include<stdio.h> void binarysearch(int arr[], int Length, int t); int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; int Length = sizeof(arr) / sizeof(arr[0]); // 计算数组长度 int t = 0; scanf("%d", &t); binarysearch(arr, Length, t); return 0; } void binarysearch(int arr[], int Length, int t) // 数组、数组长度和要查找的数 { int find = -1;//标记 int Left = 0; // 左边界 int Right = Length - 1; // 右边界 int Middle = 0; // 中间值 while (Left <= Right) // Left > Right ,表示没有找到，循环结束。 { Middle = Left + (Right - Left) / 2; if (arr[Middle] == t) // 找到了 { find = 1; break; } else if (arr[Middle] > t) // 右侧都大于t Right = Middle - 1; else // 左侧都小于t Left = Middle + 1; } if (1 == find) printf("找到了，下标为：%d\n", Middle); else printf("没有找到\n"); }
