Loading...
墨滴

李先生

2021/05/27  阅读:48  主题:橙心

快看那个运维妹子在学算法【二分查找】

数组的查找,分为两种方法,线性查找和二分查找。

一、线性查找

线性查找是一种在数据中查找数据的算法,即便数据没有按顺序存储,也可以使用线性查找。线性查找在数据中从头开始依次往下查找。

Python代码实现:

nums = [-1035912]
target = -2
for i in range(len(nums)):
    if nums[i] == target:
        result = i
    else:
        result = -1
print(result)

二、二分查找

二分查找也是一种在数组中查找数据的算法,只能查找已经排好序的数据。二分查找通过比较数组中间的数据与目标数据的大小,可以得知目标数据是在数组的左边还是右边。

图解:
1)查找已经排好序的数组中的目标数字6

2)首先找到中间数字5

3)将5和需要查找的数字作比较5<6

4)因此可得知我们需要查找的数据在5的右边

5)在剩下的数字中查找中间数字为7

6)比较6和7

7)移除不需要的数字

8)在剩下的数字中查找中间数字,此处为6

9)6=6成功找到目标数字

Python代码实现

from typing import List
import math
def search(nums: List[int], target: int) -> int:
    low = 0                #开始的位置
    high = len(nums) - 1   #结束的位置
    while low <= high:
        mid = math.floor((low + high) / 2)    #每次取中间的位置,如果不是偶数,向下取整
        guess = nums[mid]
        if guess == target:
            return mid
        if guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
        else:
            low = mid
    return -1
nums = [-1035912]
target = -2
print(search(nums, target))

三、相关资料

leetcode二分查找:https://leetcode-cn.com/problems/binary-search/
参考书籍:
《算法图解》
《我的第一本算法书》

四、写在最后

李先生(Lemon),高级运维工程师(自称),SRE专家(目标),梦想在35岁买一辆保时捷。喜欢钻研底层技术,认为底层基础才是王道。一切新技术都离不开操作系统(CPU、内存、磁盘)、网络等。坚持输入输出,记录自己学习的点滴,在平凡中坚持前行,总有一天会遇见不一样的自己。公众号:运维汪(ID:Leeeee_Li)。

李先生

2021/05/27  阅读:48  主题:橙心

作者介绍

李先生

公众号:运维汪