二分查找的实现

缺乏、安全感 2022-08-04 12:56 153阅读 0赞

在一个有序的数组中，查找一个数，可以使用二分查找，但是这个算法也是有很多地方需要注意的。正确的写法如下所示。

int binary_search(int* array,int n,int key)
    {
    	int low = 0;
    	int high = n-1;
    	int mid;
    	if(high < low)
    		return -1;
    	while(high >= low)
    	{
    		mid = low + ((high-low)>>1);
    		if(array[mid] == key)
    			return mid;
    		else if(array[mid] > key)
    			high = mid-1;
    		else
    			low = mid+1;
    	}
    	return -1;
    }

但是对于上面的二分查找还有另外一种写法，只不过需要注意上述代码中需要注意的地方。

需要注意的地方就是：

如果high = n-1,while(high>=low)  high = middle-1;

如果high = n while(high > low) high = middle;

同时也可以使用二分查找解决查找边界的问题，查找一个数在一个有序数组中的上上界和下边界。

在STL库中有一个函数为upper\_bound函数和一个lower\_bound函数，其中第一个函数为找到一个位置，此位置是最后一个可插入此元素的位置，后一个函数是第一个不小于此元素的值。在STL源码库使用的high>low的思想，我们来继承上述的思想来实现这两个函数。

//找下限 
    int lower_bound(int* array,int low,int high,int key)
    {
    	int mid;
    	if(high< low)
    		return -1;
    	while(high>=low)
    	{
    		mid = low + ((high-low)>>1);
    		if(array[mid] < key) 
    			low = mid+1;
    		else
    			high = mid-1;
    		//cout<<mid<<endl;
    	}
    	return low;
    }
    
    int upper_bound(int* array,int low,int high,int key)
    {
    	int mid;
    	if(high < low)
    		return -1;
    	while(high >= low)
    	{
    		mid = low +((high-low)>>1);
    		if(array[mid] > key)
    			high = mid-1;
    		else
    			low = mid+1;
    	}
    	return low;
    }

在STL中也有这两个函数的实现，但是在STL中的算法，所有的迭代器都是遵循左闭右开的原则，所以在哪里的首先都是high>low,然后再循环中使用的都是high = mid这种思想，在这里使用的都是左闭右闭的原则，所以使用的都是high  = mid-1这个做法。