二分查找问题

简单的二分查找问题详解

1、leetcode二分查找问题题目

由于编程水平极低，所以最近在练习leetcode上面的题目来强化自己的编程能力。遇到了这样一道题目，如下所示。

这种办法对目前的我来说有两种思路：1、顺序遍历，不过这种方法虽然直观简单但是比较暴力，用时较多。2、在题目中可以看到是一个排序好的数组，因此可以使用二分查找算法。下面分享一下我在做这道题的时候遇到的一些问题。

2、 二分查找算法

二分查找算法也叫做折半查找，思路很简单，具体的可以百度查阅相关文献，此处不做具体的阐述。二分查找法看似思路简单，实则里面有一些小坑，第一次我编写的代码如下：

int searchInsert(int* nums, int numsSize, int target)
{    
	int max = numsSize-1;    
	int mid = 0;    
	int min = 0;    
	if(nums[numsSize-1] < target)        
		return (numsSize);    
	if(nums[numsSize-1] == target)        
		return (numsSize-1);
	while(min <= max)    
	{        
		mid = min + (max - min)/2;          
		if(nums[mid] == target)             // 如果相等则直接返回        
		{            
			return mid;        
		}        
		else if(nums[mid] < target)         //说明target在mid的右边       
		{            
			min = mid + 1；		    // 更改左边界
		}        
		else                                //target在mid的左边      
		{            
			max = mid - 1;        	    //更改右边界
		}
    
	}
	        
	return (min);
}

上面的代码可以实现功能并通过了提交。但是：
在上面的代码里面，考虑到：1、可能目标并没有在数组里面，所以先判断了数组的最后一个元素；2、考虑到利用二分查找算法可能无法处理数组的最后一个元素，所以紧接着又判断了最后一个元素是否为target。但实际上后面的程序表明这两个考虑是多余的，通过一定的算法设计就能规避这两个问题。下面是新的解决办法。但是，比较上面两种，其实仅仅是把上面的两个考虑问题删除了。因为在while循环中就能避免这两个考虑.

int searchInsert(int* nums, int numsSize, int target)
{    
	int max = numsSize-1;
    	int mid = 0;  
    	int min = 0;
    	
    	while(min <= max)    
    	{        
  		mid = min + (max - min)/2;	    //二分查找公式          
  		if(nums[mid] == target)             // right        
  		{            
  			return mid；
		}        
		else if(nums[mid] < target)         //right        
		{            
			min = mid + 1;
		}        
		else                                //right        
		{            
			max = mid - 1;        
		}   
	}        

	return (min);
}

3、上下边界min和max的两种情况：

3.1、minxxxmax : max和min之间包含一个元素

这种情况下，max-min = 2 , mid = min + (max - min)/2 = xxx, 如果nums[mid] == target, 则表示找到了元素，直接返回mid即可。但是如果没有找到，则分为两种情况。1、nums[mid] < target : 这种情况下，min = mid + 1，此时，min和max直接没有元素。即是： minmax 这种情况。在这种情况下，首先， mid = min，先判断min所在的元素是否等于target，等则直接返回，如果不等，则min == mid + 1，此时min == max，再进行一次循环，mid == max， 然后判断，如果相等，则返回mid，如果不等，则target位于两者之间。并且此时max = mid - 1， 此时会造成 min > max， 循环结束。 此时target应该返回的位置就是min所在的位置。