欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找问题

程序员文章站 2022-06-02 21:25:04
...


简单的二分查找问题详解

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所在的位置。

相关标签: leetcode