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

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

 

 

Python代码实现：

  1. nums = [-1, 0, 3, 5, 9, 12]
  2. target = -2
  3. for i in range(len(nums)):
  4.     if nums[i] == target:
  5.         result = i
  6.     else:
  7.         result = -1
  8. print(result)

 

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

 

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

 

2）首先找到中间数字5

 

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

 

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

 

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

 

6）比较6和7

 

7）移除不需要的数字

 

8）在剩下的数字中查找中间数字，此处为6

 

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

 

Python代码实现

  1. from typing import List
  2. import math
  3. def search(nums: List[int], target: int) -> int:
  4.     low = 0                #开始的位置
  5.     high = len(nums) - 1   #结束的位置
  6.     while low <= high:
  7.         mid = math.floor((low + high) / 2)    #每次取中间的位置，如果不是偶数，向下取整
  8.         guess = nums[mid]
  9.         if guess == target:
  10.             return mid
  11.         if guess < target:
  12.             low = mid + 1
  13.         elif guess > target:
  14.             high = mid - 1
  15.         else:
  16.             low = mid
  17.     return -1
  18. nums = [-1, 0, 3, 5, 9, 12]
  19. target = -2
  20. print(search(nums, target))

 

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

 

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

版权声明：本文为lemon-le原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/lemon-le/p/14817786.html