[算法模板]二分查找
二分查找
1 简介
二分查找是在有序表中搜索元素的算法，比较常见。需要注意的就是二分的前提是有序，否则无法应用二分查找。
2 算法模板
以升序为例，二分查找C++模板如下：
/*二分查找C++模板@param vec : 升序数组@param left : 左边界下标，能取到@param right : 右边界下标，取不到，即[left, right)@param target : 目标值@return ans : target在vec中下标，若没有ans则为-1*/int BinarySearch(vector<int> vec, int left, int right, int target){int mid;int res = -1;while (left < right) {mid = left + (right - left) / 2;if (vec[mid] == target) {res = mid;break;} else if (vec[mid] > target) {right = mid; // [left, mid)区间继续寻找} else {left = mid + 1; // [mid + 1, right)区间继续寻找}}return res; // -1表示未找到target}
3 例题
Leetcode 74 Search a 2D Matrix
4 参考资料
[1] 算法竞赛入门经典（第二版）