数据结构-二分查找

简介: 数据结构-二分查找

1.二分查找


给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:


输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

示例 2:


输入: nums = [-1,0,3,5,9,12], target = 2


输出: -1


def binary_search(li,target):
       # 定义左右边界
       left=0
       right=len(li) - 1
       while (left <= right):
            mid = left + (right - left) // 2 # 防止溢出
            if li[mid] > target:
                right = mid - 1 # 这里等于减1是因为上面我们用的小于等于此时该mid数已经判断过
            elif li[mid] < target:
                left = mid + 1   # 同理
            else:
                return mid
                return -1


2.在排序数组中查找元素的第一个和最后一个位置


给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。


你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。


首先这个题目分为三种情况,1.待查找目标值在数组中例如:[1,2,3,5,5,6,7] target=5


此时返回值为:[3,4] 2.待查找目标值不在数组中但其大小范围在li中,[1,2,3,5,5,6,7] target=4


3,待查找目标值不在数组中且不在li范围内,[1,2,3,5,5,6,7] target=8 。2,3两种情况此时都返回[-1,-1]


def search(li,target):
        def search_LeftBorder(li,target):
                left = 0
                right = len(li)-1
                leftBorder=-2
                while (left<=right):
                    mid = left+(right-left)//2
                    if (li[mid]>=target):
                        right-=1
                        leftBorder=right  # 当li[mid]=target的时候更新right
                    else:
                        left-=1
                return leftBorder
        def search_RightBorder(li,target):
                left = 0
                right = len(li)-1
                rightBorder=-2
                while (left<=right):
                    mid = left+(right-left)//2
                    if (li[mid]>target):
                        right-=1
                    else:
                        left-=1   # 当li[mid]=target的时候更新left
                        rightBorder=left 
                return rightBorder
        leftBorder = search_LeftBorder(li,target)
        rightBorder = search_LeftBorder(li,target)
        if leftBorder==-2 or rightBorder==-2:
            return [-1,-1]
        elif (rightBorder-leftBorder)>1:
            return [leftBorder+1,rightBorder-1]
        return [-1,-1]


3.X的平方根


给你一个非负整数 x ,计算并返回 x 的 算术平方根


由于返回类型是整数,结果只保留  整数部分 ,小数部分将被 舍去


注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。


def mySqrt(x):
        if x<=1:    return x
        left,right=0,x
        while right>=left:
            mid =left+(right-left)//2
            if mid *mid <=x:
               left=mid+1
            else:
                right = mid-1
        return right


4. 有效的完全平方数


给你一个正整数 num 。如果 num 是一个完全平方数,则返回 true ,否则返回 false 。


完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。


不能使用任何内置的库函数,如  sqrt 。


def isPerfectSquare(num):
        right=num
        left=0
        s=False
        while (right>=left):
            mid = left+(right-left)//2
            if mid * mid > num:
                right = mid -1
            elif mid * mid < num:
                left = mid+1
            elif mid *mid ==num:
                s=True
                break
        return s
相关文章
数据结构上机实验之二分查找
数据结构上机实验之二分查找
|
6月前
|
机器学习/深度学习
数据结构实验之查找四:二分查找
数据结构实验之查找四:二分查找
|
6月前
|
算法 JavaScript 前端开发
JavaScript算法和数据结构:写一个二分查找的函数。
JavaScript算法和数据结构:写一个二分查找的函数。
49 0
|
算法
数据结构与算法之经典算法《二分查找》
数据结构与算法之经典算法《二分查找》
43 0
|
28天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
17 0
|
5月前
|
机器学习/深度学习 算法 索引
数据结构算法--1 顺序查找二分查找
**顺序查找时间复杂度为O(n)**,适合无序列表,可以通过`enumerate`或直接遍历索引来实现。**二分查找时间复杂度为O(logn)**,适用于有序列表,利用Python中`left`、`right`指针和`mid`点不断缩小搜索范围。效率上二分查找更优。
|
5月前
|
算法
数据结构和算法学习记录——时间复杂度的计算(嵌套循环、大O的渐进表示法、双重循环、常数循环、strchr、冒泡排序、二分查找、斐波那契数列递归)
数据结构和算法学习记录——时间复杂度的计算(嵌套循环、大O的渐进表示法、双重循环、常数循环、strchr、冒泡排序、二分查找、斐波那契数列递归)
410 1
|
6月前
|
算法 索引
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
|
6月前
|
机器学习/深度学习 算法 Java
【数据结构查找算法篇】----二分查找【实战项目】
【数据结构查找算法篇】----二分查找【实战项目】
74 1
|
6月前
【手撕数据结构】二分查找(好多细节)
【手撕数据结构】二分查找(好多细节)