二分查找边界问题总结

系统管理员 2022-11-08 11:26 122阅读 0赞

这篇总结主要是针对刷题过程中的遇到的各种二分的边界问题及常见二分类型，主要是参考了别人的博客思想，自己只是记录下来固定自己的二分模板，几点声明：

*  以下代码均采用闭区间，即`[left, right]`
 *  取中间值采用了位运算，如果边界不能保证不含负奇数，则位操作会有问题，具体可参考：[计算机中右移一位和除以二的区别][Link 1]
 *  以下的二分算法后面四种类型都是前三种的变形，所以主要理解前三种的思想和边界控制  
    
    
    ### 文章目录 ###
    
     *   *  一、基础版
         *   *  查找 target 是否存在
             *  查找大于等于 target 的第一个数
             *  查找大于 target 的第一个数
         *  二、变形版
         *   *  查找小于 target 的最后一个数
             *  查找小于等于 target 的最后一个数
             *  查找 target 最小下标
             *  查找 target 最大下标
         *  三、测试函数

## 一、基础版 ##

### 查找 target 是否存在 ###

int binarySearch(std::vector<int>& vec, const int target)
    { 
    	int left = 0;
    	int right = vec.size() - 1;
    
    	while (left <= right) { 
    		int mid = left + ((right - left) >> 1);
    		if (target == vec[mid]) { 
    			return mid;
    		}
    		else if (target < vec[mid]) { 
    			right = mid - 1;
    		}
    		else { 
    			left = mid + 1;
    		}
    	}
    
    	return -1;
    }

### 查找大于等于 target 的第一个数 ###

int firstGreaterEqual(std::vector<int>& vec, const int target)
    { 
    	int left = 0;
    	int right = vec.size() - 1;
    
    	while (left <= right) { 
    		int mid = left + ((right - left) >> 1);
    		if (target <= vec[mid]) { 
    			right = mid - 1;
    		}
    		else { 
    			left = mid + 1;
    		}
    	}
    
    	return left < vec.size() ? left : -1;
    }

### 查找大于 target 的第一个数 ###

int firstGreater(std::vector<int>& vec, const int target)
    { 
    	int left = 0;
    	int right = vec.size() - 1;
    
    	while (left <= right) { 
    		int mid = left + ((right - left) >> 1);
    		if (target < vec[mid]) { 
    			right = mid - 1;
    		}
    		else { 
    			left = mid + 1;
    		}
    	}
    
    	return left < vec.size() ? left : -1;
    }

## 二、变形版 ##

### 查找小于 target 的最后一个数 ###

// 修改： 查找大于等于 target 的第一个数
    int lastLess(std::vector<int>& vec, const int target)
    { 
    	int left = 0;
    	int right = vec.size() - 1;
    
    	while (left <= right) { 
    		int mid = left + ((right - left) >> 1);
    		if (target <= vec[mid]) { 
    			right = mid - 1;
    		}
    		else { 
    			left = mid + 1;
    		}
    	}
    
    	return (left - 1 >= 0) ? left - 1 : -1;
    }

### 查找小于等于 target 的最后一个数 ###

// 修改：查找大于 target 的第一个数
    int lastLessEqual(std::vector<int>& vec, const int target)
    { 
    	int left = 0;
    	int right = vec.size() - 1;
    
    	while (left <= right) { 
    		int mid = left + ((right - left) >> 1);
    		if (target < vec[mid]) { 
    			right = mid - 1;
    		}
    		else { 
    			left = mid + 1;
    		}
    	}
    
    	return (left - 1 >= 0) ? left - 1 : -1;
    }

### 查找 target 最小下标 ###

// 修改： 查找大于等于 target 的第一个数，返回值需要做判断
    int lowBound(std::vector<int>& vec, const int target)
    { 
    	int left = 0;
    	int right = vec.size() - 1;
    
    	while (left <= right) { 
    		int mid = left + ((right - left) >> 1);
    		if (target <= vec[mid]) { 
    			right = mid - 1;
    		}
    		else { 
    			left = mid + 1;
    		}
    	}
    
    	return (left < vec.size() && vec[left] == target) ? left : -1;
    }

### 查找 target 最大下标 ###

// 修改：查找大于 target 的第一个数，返回值需要做判断
    int highBound(std::vector<int>& vec, const int target)
    { 
    	int left = 0;
    	int right = vec.size() - 1;
    
    	while (left <= right) { 
    		int mid = left + ((right - left) >> 1);
    		if (target < vec[mid]) { 
    			right = mid - 1;
    		}
    		else { 
    			left = mid + 1;
    		}
    	}
    
    	return ((left - 1 >= 0) && vec[left - 1] == target) ? left - 1 : -1;
    }

## 三、测试函数 ##

/*------------------------------------------------------------/ * @file main.cpp * @brief * * @author DuYong * @date 2021-3-13 *-----------------------------------------------------------*/
    
    #include "binary_search.h"
    
    void test()
    { 
    	std::vector<int> vec{  1, 2, 2, 2, 4, 8, 10 };
    	int target{  2 }, index{  -1 };
    
    	// index = binarySearch(vec, target); // index is: 3
    
    	// index = firstGreaterEqual(vec, target); // index is: 1
    
    	// index = firstGreater(vec, target); // index is: 4
    
    	// index = lastLess(vec, target); // index is: 0
    
    	// index = lastLessEqual(vec, target); // index is: 3
    
    	// index = lowBound(vec, target); // index is: 1
    
    	// index = highBound(vec, target); // index is : 3
    
    
    	std::cout << "index is: " << index << std::endl;
    
    	return;
    }
    
    int main()
    { 
    	test();
    
    	system("pause");
    	return 0;
    }

参考博客：

*  [二分查找各种情况大总结][Link 2]
 *  [七种二分查找变形情况合集，核心思想不变!][Link 3]

[Link 1]: https://blog.csdn.net/weixin_42482896/article/details/114701167?spm=1001.2014.3001.5501
[Link 2]: https://blog.csdn.net/yefengzhichen/article/details/52372407
[Link 3]: https://blog.csdn.net/Hide_in_Code/article/details/76549317