每日一题01

每日一题

二分查找

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