每日一题
二分查找
leetcode 704 二分查找
https://leetcode.cn/problems/binary-search/
题解：
CPP:
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left < right){
int middle = left + right >> 1;
if(nums[middle] >= target){
right = middle;
}else{
left = middle + 1;
}
}
if(nums[left] == target) return left;
return -1;
}
};
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left < right){
int middle = left + right + 1 >> 1;
if(nums[middle] > target){
right = middle - 1;
}else{
left = middle;
}
}
if(nums[left] == target) return left;
return -1;
}
};
python:
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0,len(nums) - 1
while left < right:
middle = left + right + 1 >> 1
if nums[middle] > target:
right = middle - 1
elif nums[middle] <= target:
left = middle
if nums[left] == target:
return left
return -1
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0,len(nums) - 1
while left < right:
middle = left + right >> 1
if nums[middle] >= target:
right = middle
elif nums[middle] < target:
left = middle + 1
if nums[left] == target:
return left
return -1
leetcode 35.搜索插入位置
https://leetcode.cn/problems/search-insert-position/
代码：
cpp：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
if(nums[left] > target) return left;
while(left < right){
int middle = left + right + 1 >> 1;
if(nums[middle] > target){
right = middle - 1;
}else{
left = middle;
}
}
if(nums[left] == target) return left;
return left + 1;
}
};
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
if(nums[right] < target) return right + 1;
while(left < right){
int middle = left + right >> 1;
if(nums[middle] >= target){
right = middle;
}else{
left = middle + 1;
}
}
return left;
}
};
python:
class Solution(object):
def searchInsert(self, nums, target):
left, right = 0, len(nums) - 1
if target > nums[right]:
return right + 1
while left < right:
middle = left + right >> 1
if nums[middle] >= target:
right = middle
else:
left = middle + 1
return left
class Solution(object):
def searchInsert(self, nums, target):
left, right = 0, len(nums) - 1
if target < nums[left]:
return left
while left < right:
middle = left + right + 1 >> 1
if nums[middle] <= target:
left = middle
else:
right = middle - 1
if nums[left] == target:
return left
return left + 1
leetcode 34.在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
cpp
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0) return {-1, -1};
int left = 0;
int right = nums.size() - 1;
int leftborder;
int rightborder;
while(left < right){
int middle = (left + right) >> 1;
if(nums[middle] >= target){
right = middle;
}else{
left = middle + 1;
}
}
leftborder = left;
if(nums[leftborder] != target) return {-1, -1};
else
{
left = 0;
right = nums.size() - 1;
while(left < right){
int middle = (left + right + 1) >> 1;
if(nums[middle] > target){
right = middle - 1;
}else{
left = middle;
}
}
rightborder = left;
}
return {leftborder, rightborder};
}
};
python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if len(nums) == 0:
return [-1, -1]
left, right = 0, len(nums) - 1
while left < right:
middle = left + right >> 1
if nums[middle] >= target:
right = middle
else:
left = middle + 1
if nums[left] != target:
return [-1, -1]
else:
leftboarder = left
left = 0
right = len(nums) - 1
while left < right:
middle = left + right + 1 >> 1
if nums[middle] > target:
right = middle - 1
else:
left = middle
rightborder = left
return [leftboarder, rightborder]
leetcode 69.x的平方根
https://leetcode.cn/problems/sqrtx/
cpp
class Solution {
public:
int mySqrt(int x) {
if(x <= 1) return x;
int left = 0;
int right = x / 2 + 1;
while(left < right){
int middle = (left + right) >> 1;
if((long long)middle * middle <= x){//注意需要进行类型转换，防止int类型无法表示乘积
left = middle + 1;
}else{
right = middle;
}
}
return left - 1;
}
};
python
class Solution:
def mySqrt(self, x: int) -> int:
if x <= 1:
return x
left, right = 0, x // 2 + 1
while left < right:
middle = (left + right) // 2
if middle * middle <= x:
left = middle + 1
else:
right = middle
return int(left - 1)
#需要注意python支持高精度，需要使用整除来表示除法
leetcode367. 有效的完全平方根
https://leetcode.cn/problems/valid-perfect-square/
cpp
class Solution {
public:
bool isPerfectSquare(int num) {
long left = 1;
long right = num / 2;
while(left < right){
long middle = (left + right) / 2;
if(middle * middle == num) return true;
if(middle * middle < num){
left = middle + 1;
}else{
right = middle - 1;
}
}
if (left*left == num) return true;
return false;
}
};
python
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left, right = 1, num // 2
while left < right:
middle = (left + right) // 2
if middle * middle == num:
return True
if middle * middle > num:
right = middle - 1
else:
left = middle + 1
if left * left == num:
return True
return False