引入：
二分法思想无处不在，我们经常玩的猜数字游戏，0-99的范围，最多需要多少次我就可以猜对呢？
使用二分法思想，最多仅仅需要7次就可以查找到。
二分法查找是非常恐怖的，以2的倍数缩小范围。所以时间复杂度O(logn)
局限性：
1.针对二分法查找的数据必须是有序的。
2.二分法查找依赖于顺序表结构，也就是数组。因为二分法需要随机访问元素，也就是O(1)的复杂度找到对象，所以需要内存连续。如果使用链表，那么时间复杂度就会变得非常高
3.适合静态数据，不适合频繁的插入和删除操作的数据所以当数据比较静态，没有频繁的插入和删除的操作的时候，可以先对数据进行排序，排序时间复杂度最低O(nlogn)
例子：
求一个数的平方根，可以指定精度。
从二分法的思想就是不断的范围缩减，所以代码实现上可以有通过递归的方式和非递归的方式实现。
class Program { static void Main(string args) { var data = GetSS(4, 0.00000001); Console.WriteLine(data*data); } /// <summary> /// 获取平方根 /// </summary> /// <param name="input">输入值</param> /// <param name="jd">精度</param> /// <returns></returns> public static double GetSS(double input, double jd) { double low = 0; double high = input; double middle = low + (high - low) / 2; while ((high - low) > jd) { if (input > middle * middle) { low = middle; } else { high = middle; } middle = low + (high - low)/2; Console.WriteLine(high - low); } return middle; } }
问题深入
上面的使用二分法查找都是最简单的情况，也就是数据不存在重复的情况下，但是数据如果存在重复的情况下，会出现其他的变种的需求;
(1)查找第一个元素等于给定值的元素
static void Main(string args) { var a = new { 1,2,8,8,8,8,8,8,11,13,18}; Console.WriteLine(GetValue(a, a.Length,8)); } public static int GetValue(int a,int n ,int value) { var low = 0; var high = n - 1; while (low <= high) { int middle = low + ((high - low) >> 1); if (a > value) {//因为不包含等于，可以多递增一个数 high = middle-1; } else if (a < value) { low =middle+1; } else { if (middle == 0 || a[middle - 1] != value) { return middle; } else { //因为是查找第一个所以将high赋值middle-1 high = middle-1; } } } return -1; }
上面的代码就是当a=value的时候，需要判断一下middle-1的值是否是指定值。
（2）查找最后一个等于给定值的元素。
这个就比较简单了，只要在第一个的基础上稍作修改即可
public static int GetValue(int a, int n, int value) { var low = 0; var high = n - 1; while (low <= high) { int middle = low + ((high - low) >> 1); if (a > value) {//因为不包含等于，可以多递增一个数 high = middle - 1; } else if (a < value) { low = middle + 1; } else { if (middle == 0 || a[middle +1] != value) { return middle; } else { low = middle + 1; } } } return -1; }
（3）查找第一个大于等于给定值的元素
public static int GetValue(int a, int n, int value) { var low = 0; var high = n - 1; while (low <= high) { int middle = low + ((high - low) >> 1); if (a >= value) {//因为不包含等于，可以多递增一个数 if (middle == 0 || a[middle - 1] < value) { return middle; } else { high = middle - 1; } } else { low = middle + 1; } } return -1; }
（4）查找最后一个小于等于给定值的元素
public static int GetValue(int a, int n, int value) { var low = 0; var high = n - 1; while (low <= high) { int middle = low + ((high - low) >> 1); if (a > value) {//因为不包含等于，可以多递增一个数 high = middle - 1; } else { if (middle == 0 || a[middle + 1] > value) { return middle; } else { low = middle +1; } } } return -1; }
本文【二分法查找是什么意思】由作者： 自旋锁 提供，本站不拥有所有权，只提供储存服务，如有侵权，联系删除！
本文链接：https://www.cuoshuo.com/blog/4284.html
