二分查找算法

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

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0)return {-1, -1};vector<int> ret;// 找左int left = 0;int right = nums.size() - 1;while (left != right){int mid = (right + left) / 2; // 落在左边if (nums[mid] < target)left = mid + 1;else if (nums[mid] >= target)right = mid;}if(nums[left] == target)ret.push_back(left);else ret.push_back(-1);// 找右left = 0;right = nums.size() - 1;while (left != right){int mid = (right + left + 1) / 2; // 落在右边if (nums[mid] <= target)left = mid;else if (nums[mid] > target)right = mid - 1;}if(nums[left] == target)ret.push_back(left);else ret.push_back(-1);return ret;}
};

class Solution {
public:int mySqrt(int x) {if(x == 0)return 0;int left = 1;int right = x;while(left != right){long long mid = left + (right - left + 1) / 2; // 防止溢出if(mid * mid <= x)left = mid;else if(mid * mid > x)right = mid - 1;}return left;}
};