代码随想录一一一数组一一一二分查找

题目来源自leetcode与代码随想录

（1）704.有序列表数据的二分查找

题目：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
解题思路：
确定当前数据范围为[left, right]=[0, len(num)-1],左闭右闭。则终止条件的left应该小于等于right。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1

        while left <= right:
            middle = left + (right-left)//2

            if nums[middle] == target:
                return middle
            elif nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            else:
                pass

        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（2）35.有序表搜索插入位置

题目：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
解题思路：
同样是有序表的二分查找，如果查找元素在表中，返回位置结束，如果查找元素不在表中，左右两个指针最后会停止在两个元素最为纠结的区间，停止的条件就是left = right + 1，所以此时返回两个值任意一个即可

class Solution(object):
    def searchInsert(self, nums:list[int], target:int) -> int:

        low, high = 0, len(nums)-1
        
        while low <= high:
            middle = low + (high-low)//2
            # print("1", low, middle, high)
            if nums[middle] > target:
                high = middle-1

            if nums[middle] < target:
                low = middle+1
                
            if nums[middle] == target:
                return middle
            # print("2", low, middle, high)
        return low
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（3）69.计算x的算术平方根

题目：
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
解题思路：
其实就是将一个二分的线性查找变为了平方计算，移动的单位从单位“1”变为了“x^2”,只需要在[0,x]这个区间中找mid，mid*mid和target比较即可

class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:
            return x

        low, high = 1, x
        
        while low <= high:
            middle = low + (high-low)//2
            if middle*middle > x:
                high = middle-1

            elif middle*middle < x:
                low = middle+1
                
            else: #if middle*middle == x:
                return middle

        return low-1 or high
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（4） 367.有效的完全平方数

题目：
判断是否为完全平方数
解题思路：
与（3）完全相同，只是将返回值修改为布尔值即可

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        low, high = 1, num
        
        while low <= high:
            middle = low + (high-low)//2

            if middle*middle > num:
                high = middle-1

            elif middle*middle < num:
                low = middle+1
                
            else: #if middle*middle == x:
                return True

        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17