在做Leetcode74 搜索二维矩阵时,我的算法对二分查找有一个进阶要求。
二分查找的板子是直接找该元素在不在线性表内。
如果我希望在进行二分查找的时候,即使该元素不在线性表内,我想找到它介于哪两个元素之间,怎么写。
class Solution {
public:bool searchMatrix(vector<int>& v, int target) {int left = 0,right = matrix.size()-1;int near_left = left,near_right = right;while(left <= right){int mid = left + (right - left) / 2;if (target < v[mid]) {near_right = mid;right = mid - 1;}else if (target > v[mid]){near_left = mid;left = mid + 1;}else return 1; // 已找到}cout<< "左紧邻下标:" << near_left << endl;cout<< "右紧邻下标:" << near_right << endl;return 0; // 未找到}
};