二分查找(一)
二分查找看似简单，但是有很多的细节要注意。
题目是牛客NC105，找到有序数组中第一个大于或者等于所查找的数字。
初步写了如下的代码：
class Solution {
public:
/**
* 二分查找
* @param n int整型 数组长度
* @param v int整型 查找值
* @param a int整型vector 有序数组
* @return int整型
*/
int upper_bound_(int n, int v, vector<int>& a) {
// write code here
int mid=0;
int left=0;
int right=n-1;
while(left < right)
{
//mid = left+(right-left)/2;
mid = (left+right)/2;
if(a[mid] > v){
if(a[mid-1]<v) return mid;
else{
right = mid-1;
}
}else if(a[mid] < v){
left = mid+1;
}else if(a[mid] == v)
{
while(a[mid] == v){
mid--;
}
return mid+1;//这里必须是mid+1？
}
}
return n+1;
}
};
运行之后发现测试用例不能完全通过，这段代码有什么问题？
首先是mid = left + (right-left)/2, 这和mid = (left+right)/2相比，有什么区别？
实际测试的时候，没有区别，但是一旦left和right都很大的时候，则有可能会造成数组越界。
因此，使用(right-left)/2可以很大程度避免两个很大的数相加导致数组越界的情况发生。
其次是把right=mid写成了right=mid-1。为什么？
因为a[mid]>v的情况下，a[mid]是符合题目要求的大于所查找数的，所以，right=mid,而不是right=mid-1。也就是说，没有把它排除。
代码还有bug,
while(a[mid] == v)
{
mid--;
}
return mid+1;
把return mid+1改为了return mid+2,因为输出是按1而不是按0开始的。
我的解题思路是，如果是大于v,则判断其左侧的位置是否小于v,如果小于则是第一个，如果等于v,则不断向左移动，直到找到小于v的位置。
标准题解：
标准题解把a[mid]>=v放到一起作为判断条件。这是因为既然是大于等于，则a[mid]>=v都是符合要求的，只要判断是不是第一次即可。
什么是第一次呢？ 那就是mid左边的那个数如果是小于v的，则mid就是符合要求的。二分查找的本质，是left在等于right之前，不断查找符合条件的位置。
mid发现的位置是中间位置而不是'第一次'出现的位置。因为大于等于所找的值，这本身就是符合要求的条件，二分查找找的就是符合某条件的位置，不断地通过二分查找直到找到。
因此 a[mid]>=v可以写在一起。
最后经过优化的代码：
int upper_bound_(int n, int v, vector<int>& a) {
// write code here
int mid=0;
int left=0;
int right=n-1;
while(left < right)
{
mid = left+(right-left)/2;//为什么要这样写Mid?
if(a[mid] > v){
if( mid == 0|| a[mid-1]<v) return mid+1;
else{
right = mid;
}
}else if(a[mid] < v){
left = mid+1;
}else if(a[mid] == v)
{
if(a[mid-1]<v)
return mid+1;
else right = mid;
}
}
return n+1;
}
如果是left <=right呢？修改之后仍不会影响结果。
做完该题后，再看leetcode 704
class Solution {
public:
int search(vector<int>& nums, int target) {
int len = nums.size();
int left = 0;
int right = len-1;
int mid = 0;
while(left < right)//如果只有一个元素会如何呢？
{
mid = left + (right-left)/2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target)
{
right = mid - 1;
}else if(nums[mid] < target)
{
left = mid + 1;
}
}
return -1;
}
};
这段代码无法通过全部的测试用例，比如在测试元素只有一个的数组的时候报错了，因此要怎么办？
最好是用while(left<=right),这样就避免了一个元素时不进入循环的情况了。
继续趁热打铁，看leetcode 74题，搜索二维矩阵。
获取二维数组的行和列
行数 = sizeof(array)/sizeof(array[0])
列数 = sizeof(array[0])/sizeof(array[0][0])
行数计算方法就是用二维数组的整个size除以第一行的size
列数计算方法就是第一行除以每个元素的size.
求vector二维数组的行数，直接就是size()方法。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
//只要先按照第一列进行二分查找，找到第一个大于等于的位置，然后该位置的
//上一个数组就可能存在一个目标值，在在数组中继续二分查找。
//行数
//int m = sizeof(matrix)/sizeof(matrix[0]);
int m = matrix.size();//直接就是行数
int up = 0;
int down = m-1;
int mid1=0;
while(up <= down)
{
mid1 = up+(down-up)/2;
if(matrix[mid1][0] == target){
return true;
}else if(matrix[mid1][0] > target){
if(matrix[mid1-1][0] < target){//上一行中必然存在,mid1-1行可能存在
break;
}else{
down = mid1 -1 ;
}
}else if(matrix[mid1-1][0] < target){
up = mid1 + 1;
}
}
int n = matrix[0].size();
int left = 0;
int right = n-1;
int mid2 = 0;
while(left <= right)
{
mid2 = left+(right-left)/2;
if(matrix[mid1-1][mid2] == target){
return true;
}else if(matrix[mid1-1][mid2] > target)
{
right = mid2-1;
}else if(matrix[mid1-1][mid2] < target)
{
left = mid2+1;
}
}
return false;
}
};
以上代码有什么错误？
没有考虑到空参数的问题，会出现'runtime error: reference binding to null pointer of type'提示。
如果是[[]] ， 二维数组的特殊情形， 完全空，只有一行一列，多行一列，一行多列。这四种情况，都要在运行的时候考虑到。
因此，最稳妥的方式就是把二维数组转化为一维数组。但是一维数组有没有最大长度？ 有，vector是有最大长度的。https://blog.csdn.net/iceboy314159/article/details/80329979
但是在本题中足够。
标准题解：
也不需要先将二维放入一维徒增空间复杂度，而是直接把二维数组当成一维数组。
a[mid]转换就是b[mid/n][mid % n],为什么？ 第k个数是在二维数组种的位置便是[k / n][k % n]。
这里的k包括了从0位置开始的记录。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
//转化为一维数组，但是要考虑到长度问题。
int m = matrix.size();
int n = matrix[0].size();
if( m == 0 || n == 0) return false;
int left = 0;
int right = m*n-1;
int mid = 0;
while(left <= right)
{
mid = left+(right-left)/2;
int tmp = matrix[mid/n][mid%n];
if(tmp > target){
right = mid - 1;
}else if(tmp < target)
{
left = mid + 1;
}else
return true;
}
return false;
}
};
这一块代码为什么还有问题？ 输入了[]之后，还是会有错误？
因为输入了[]之后，其中这不是二维数组，所以行数为0，而行数为0的情况下判断martix[0].size()就是不可能的。
所以应该先判断行数是否存在，存在后再计算列数。
改代码为：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
//转化为一维数组，但是要考虑到长度问题。
int m = matrix.size();
if(m == 0) return false;
int n = matrix[0].size();
if( n == 0) return false;
int left = 0;
int right = m*n-1;
int mid = 0;
while(left <= right)
{
mid = left+(right-left)/2;
int tmp = matrix[mid/n][mid%n];
if(tmp > target){
right = mid - 1;
}else if(tmp < target)
{
left = mid + 1;
}else
return true;
}
return false;
}
};
当然，这样做的时间复杂度是MN，而空间复杂度为1.有没有更好的方法呢？ 那就是前面提到的先判断在哪一行，再判断是该行的哪一列。
加上了对二维数组的判空后，第一种做法仍然会报错，这是由于还有1行1列，1行多列的情况存在，这种情况下，mid-1就会出现负值，导致出错。
这样的话，判断条件非常多，所以不选择在第一列找，而是在最后一列找，在最后一列找到第一次大于target的，则找到的mid就是可能存在该数的行。
二分查找中遇到Mid==0该怎么办
mid为0的情况，比如前一个mid为1，但是还是不满足条件，然后再次除以2，从而mid==0,此时left和right也相等，则不需要再查找，而是直接跳出。
还有一种情况，就是只有一个元素的数组。总之，mid为0表示之后不需要再次计算。