二分法小结

二分法是一个神奇的东西，弄了半天，总算知道怎样合理的去使用了

常规的二分法正确的时候返回正确的下标或值，在找不到的情况下，返回比要查找的数稍大点的数(已排序），

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int b = 4, a[] = { 2,6,7 };
 7     int i = 0, j = 2;
 8     while (i < j)
 9     {
10         int mid = i + (j - i) / 2;
11         if (a[mid] >= b) j = mid;
12         else i = mid+1;
13     }
14     cout << "要查找的区间：" << "2 6 7 " << endl;
15     cout << "要查找的数：4" << endl;
16     cout << a[i] << endl;
17 }

而另外的一种二分，可使返回正确的值，若无，则返回尽量小的数

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int b = 4, a[] = { 2,6,7 };
 7     int i = 0, j = 2;
 8     while (i < j-1)
 9     {
10         int mid = i + (j - i) / 2;
11         if (a[mid] > b) j = mid;
12         else i = mid;
13     }
14     cout << "要查找的区间：" << "2 6 7 " << endl;
15     cout << "要查找的数：4" << endl;
16     cout << a[i] << endl;
17 }

（两种方法的不同之处在于跳出循环的条件不同）