二分查找法及延伸
|
一、二分查找 二分查找，又叫折半查找。
代码记住。
二、二分查找，如果能找到target就返回target，如果找不到target就返回比target小一点的那个数。
例如： 0 1 2 3 4 5 6 7 8 9 [1,3,4,5,7, 9 ,11,14,16, 22]
想找8。 low = 0, high = 9 mid=4, a[4] = 7<8 , low = mid+1 = 5, high = 9 mid = 7 , a[7] = 14>8 , high = mid-1 = 6 , low = 5 mid = 5 , a[5] = 9>8 , high = mid - 1 = 4 ,low = 5 high<low, 小于8的数为a[low-1]或者a[high]
再比如： 0 1 2 3 4 5 6 7 8 9 [1,3,4,5,7, 9 ,11,14,16, 22]
想找2. low = 0 ,high = 9 mid = 4 ,a[4] = 7>2。high = mid-1 = 3。 low = 0。 mid= 1,a[1]=3>2。high= mid-1 = 0。 low = 0。 mid =0, a[0] = 1<2 。 low = mid +1 =1。 high = 0. high < low，小于2的数为a[low-1]或者a[high]
再比如： 0 1 2 [1,2,3] 想找2.5。 low = 0 ,high = 2 mid = 1, a[1] = 2<2.5。 low= mid+1 = 2。 high= 2。 mid = 2 ， a[2] =3>2.5。 high = mid-1=1。low=2. high <low，小于2.5的数是a[low-1]或者a[high]
再比如： [1] 想找2。 low = 0 ,high = 0 mid = 0 , a[0]=1<2。 low = mid+1 = 2。high = 0。 high<low，小于2的数是a[low-1]或者a[high]
综上，还是使用二分查找的代码，当差找不到时，下标low-1或者high对应的值就是小于target的值。
代码：
结果： 感谢我女朋友提供的方法~~~
|