704. 二分查找

2025/2/11 7:03:10 来源：https://blog.csdn.net/m0_63056769/article/details/145556589 浏览: 次关键词：704. 二分查找

704. 二分查找 - 力扣（LeetCode）

定义左右边界为 -1 n 结束条件 left + 1 == right

注意的是 n == 1 会照成越界需要分类讨论

class Solution {int binarySearch( vector<int>& nums, int target){int n = nums.size();int right = n , left = -1, mid;while ( left + 1 != right){mid = (right + left) / 2;if ( nums[mid] < target){left = mid;}else{right = mid;}}return right;}
public:int search(vector<int>& nums, int target) {if ( nums.size() == 1 ){return nums[0] == target ? 0 : -1;}int pos = binarySearch( nums, target);return nums[pos] == target ? pos : -1;}
};

还要注意有些空数组还有很多数组越界的问题

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

class Solution {int binarySearch( vector<int>& nums, int target){int n = nums.size();int left = -1, right = n, mid;while ( left + 1 != right){mid = (left + right) / 2;if ( nums[mid] < target){left = mid;}else{right = mid;}}return right;  }
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> v = {-1, -1};int n = nums.size();if ( n == 0){  //数组元素为空return v;}if ( n == 1){  //单个元素if ( nums[0] == target){v[0] = 0, v[1] = 0;return v;}else{return v;}}int x = binarySearch( nums, target);  //区间存在 计算左区间if ( x == n ){  //该数组不存在target  提前返回( 全部比target小)return v;}else if (nums[x] != target ){  //找到比target大的 但是没有找到targetreturn v; }v[0] = x;x = binarySearch( nums, target + 1);  //区间存在 计算右区间v[1] = x - 1;  //得到右区间是该区间的右一个return v;}
};