东莞知名网站推广,为离职员工做的网站,松岗网站开发,外贸企业邮箱哪家好1. 什么是 MD5 加密#xff0c;有什么特点 要点 定义#xff1a;MD5 是一种广泛应用的哈希函数#xff0c;它能够把任意长度的输入数据经过特定算法处理#xff0c;转化为长度固定为 128 位的哈希值#xff0c;通常以 32 位十六进制字符串的形式呈现#xff0c;主要用于验…1. 什么是 MD5 加密有什么特点 要点 定义MD5 是一种广泛应用的哈希函数它能够把任意长度的输入数据经过特定算法处理转化为长度固定为 128 位的哈希值通常以 32 位十六进制字符串的形式呈现主要用于验证数据在传输或存储过程中是否保持完整未被篡改。 特点 固定输出无论输入的数据量大小如何MD5 都会生成长度统一的 128 位哈希值方便数据的存储和比较。 高效计算MD5 的计算过程相对简单执行速度快能在短时间内对大量数据完成哈希计算。 不可逆性从生成的哈希值无法反向推导出原始的输入数据保证了数据的安全性。 雪崩效应输入数据哪怕只有极其微小的改变都会使输出的哈希值发生巨大的变化这一特性增强了哈希值的唯一性和辨识度。 安全缺陷由于存在碰撞攻击的风险即可以找到两个不同的输入产生相同的哈希值MD5 已不适合用于对安全性要求较高的场景如密码存储。 python
import hashlibdef md5_encryption(data):该函数用于对输入的数据进行 MD5 加密:param data: 待加密的字符串:return: 加密后的十六进制哈希值# 创建 MD5 哈希对象md5_hash hashlib.md5()# 将输入数据编码为 UTF - 8 格式并更新哈希对象的内容md5_hash.update(data.encode(utf-8))# 获取十六进制表示的哈希值return md5_hash.hexdigest()# 定义要加密的字符串
original_data Hello, World!
# 调用函数进行加密
encrypted_data md5_encryption(original_data)print(f原始数据: {original_data})
print(fMD5 加密后的哈希值: {encrypted_data})补充知识点 1. 安全替代方案鉴于 MD5 的安全漏洞在实际应用中可使用更安全的哈希算法如 SHA - 256。以下是使用 Python 实现 SHA - 256 加密的示例代码 python
import hashlibdef sha256_encryption(data):该函数用于对输入的数据进行 SHA - 256 加密:param data: 待加密的字符串:return: 加密后的十六进制哈希值# 创建 SHA - 256 哈希对象sha256_hash hashlib.sha256()# 将输入数据编码为 UTF - 8 格式并更新哈希对象的内容sha256_hash.update(data.encode(utf-8))# 获取十六进制表示的哈希值return sha256_hash.hexdigest()original_data Hello, World!
encrypted_data sha256_encryption(original_data)print(f原始数据: {original_data})
print(fSHA - 256 加密后的哈希值: {encrypted_data})2. 批量数据验证在处理大量数据时可对每个数据块进行 MD5 哈希计算并将哈希值存储下来。在后续验证数据完整性时重新计算哈希值并与之前存储的进行比对以此判断数据是否被篡改。 2. 什么是对称加密和非对称加密 要点 1. 对称加密
原理使用相同的密钥进行数据的加密和解密操作。在通信过程中发送方和接收方需要预先共享这个密钥。常见算法包括 DESData Encryption Standard、3DESTriple DES、AESAdvanced Encryption Standard等。优缺点优点是加密和解密速度快处理效率高适合对大量数据进行加密缺点是密钥管理困难因为密钥需要在通信双方之间安全传输一旦密钥泄露数据就会面临安全风险。 2. 非对称加密 原理使用一对密钥即公钥和私钥。公钥可以公开分发任何人都可以使用公钥对数据进行加密而私钥只有拥有者知道用于解密用公钥加密的数据。 常见算法如 RSA、ECCElliptic Curve Cryptography等。 优缺点优点是密钥管理相对简单公钥可以公开无需像对称加密那样进行安全传输。同时它还可用于数字签名确保数据的真实性和不可否认性缺点是加密和解密速度相对较慢不适合对大量数据进行加密。 对称加密AES python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import osdef aes_encrypt(data, key):该函数使用 AES 算法对数据进行加密:param data: 待加密的字节数据:param key: 加密密钥字节类型:return: 加密后的字节数据# 创建 AES 加密器使用 ECB 模式cipher AES.new(key, AES.MODE_ECB)# 填充数据以满足 AES 块大小要求padded_data pad(data, AES.block_size)# 加密数据return cipher.encrypt(padded_data)def aes_decrypt(encrypted_data, key):该函数使用 AES 算法对加密数据进行解密:param encrypted_data: 加密后的字节数据:param key: 解密密钥字节类型:return: 解密后的原始数据# 创建 AES 解密器使用 ECB 模式decipher AES.new(key, AES.MODE_ECB)# 解密数据decrypted_data decipher.decrypt(encrypted_data)# 去除填充return unpad(decrypted_data, AES.block_size)# 生成 16 字节的密钥
key os.urandom(16)
# 要加密的数据
original_data bHello, AES!
# 调用加密函数
encrypted_data aes_encrypt(original_data, key)
# 调用解密函数
decrypted_data aes_decrypt(encrypted_data, key)print(f原始数据: {original_data})
print(f加密后的数据: {encrypted_data})
print(f解密后的数据: {decrypted_data})非对称加密RSA python
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEPdef rsa_encrypt(data, public_key):该函数使用 RSA 公钥对数据进行加密:param data: 待加密的字节数据:param public_key: RSA 公钥对象:return: 加密后的字节数据# 创建 RSA 加密器cipher_rsa PKCS1_OAEP.new(public_key)# 加密数据return cipher_rsa.encrypt(data)def rsa_decrypt(encrypted_data, private_key):该函数使用 RSA 私钥对加密数据进行解密:param encrypted_data: 加密后的字节数据:param private_key: RSA 私钥对象:return: 解密后的原始数据# 创建 RSA 解密器cipher_rsa PKCS1_OAEP.new(private_key)# 解密数据return cipher_rsa.decrypt(encrypted_data)# 生成 RSA 密钥对
key RSA.generate(2048)
private_key key.export_key()
public_key key.publickey().export_key()# 加载公钥
recipient_key RSA.import_key(public_key)
# 要加密的数据
original_data bHello, RSA!
# 调用加密函数
encrypted_data rsa_encrypt(original_data, recipient_key)# 加载私钥
private_key RSA.import_key(private_key)
# 调用解密函数
decrypted_data rsa_decrypt(encrypted_data, private_key)print(f原始数据: {original_data})
print(f加密后的数据: {encrypted_data})
print(f解密后的数据: {decrypted_data})补充知识点 混合加密方案结合对称加密和非对称加密的优势先使用非对称加密算法安全地传输对称加密所需的密钥然后使用对称加密算法对大量数据进行高效加密。这样既能保证密钥传输的安全性又能提高数据加密的效率。 数字签名应用拓展在实际应用中数字签名不仅可用于验证数据的真实性和不可否认性还可用于软件分发、电子合同签署等场景确保数据在传输和存储过程中的完整性和合法性。 3. 什么是冒泡排序 要点 冒泡排序是一种简单直观的排序算法其核心思想是通过多次比较相邻元素的大小若顺序错误则交换它们的位置使得较大的元素逐步 “冒泡” 到数组的末尾。具体步骤为从数组的第一个元素开始依次比较相邻的两个元素若前一个元素大于后一个元素则交换它们的位置重复这个过程直到整个数组有序。 python
def bubble_sort(arr):该函数实现冒泡排序算法:param arr: 待排序的列表:return: 排序后的列表n len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] arr[j 1]:# 交换元素位置arr[j], arr[j 1] arr[j 1], arr[j]return arr# 测试示例
original_array [64, 34, 25, 12, 22, 11, 90]
sorted_array bubble_sort(original_array)
print(f原始数组: {original_array})
print(f排序后的数组: {sorted_array})补充知识点 1. 优化冒泡排序算法在冒泡排序的基础上添加一个标志位来记录每一轮是否发生了元素交换。如果某一轮没有发生交换说明数组已经有序可以提前结束排序过程从而减少不必要的比较次数提高算法效率。以下是优化后的代码 python
def optimized_bubble_sort(arr):该函数实现优化后的冒泡排序算法:param arr: 待排序的列表:return: 排序后的列表n len(arr)for i in range(n):swapped Falsefor j in range(0, n - i - 1):if arr[j] arr[j 1]:arr[j], arr[j 1] arr[j 1], arr[j]swapped Trueif not swapped:breakreturn arroriginal_array [64, 34, 25, 12, 22, 11, 90]
sorted_array optimized_bubble_sort(original_array)
print(f原始数组: {original_array})
print(f排序后的数组: {sorted_array})2. 双向冒泡排序鸡尾酒排序在传统冒泡排序的基础上进行改进不仅从前往后比较和交换元素还从后往前进行相同的操作这样可以更快地将较大和较小的元素移到合适的位置进一步提高排序效率。 4. 什么是快速排序 要点 快速排序是一种高效的分治排序算法其基本思想是通过选择一个基准元素将数组分为两部分使得左边部分的所有元素都小于等于基准元素右边部分的所有元素都大于等于基准元素然后分别对左右两部分递归地进行排序最终得到一个有序的数组。具体步骤包括选择基准元素、进行分区操作将数组划分为两部分、对左右子数组递归排序。 python
def quick_sort(arr):该函数实现快速排序算法:param arr: 待排序的列表:return: 排序后的列表if len(arr) 1:return arrelse:# 选择第一个元素作为基准pivot arr[0]# 小于等于基准的元素组成的列表left [x for x in arr[1:] if x pivot]# 大于基准的元素组成的列表right [x for x in arr[1:] if x pivot]# 递归排序左右子数组并合并结果return quick_sort(left) [pivot] quick_sort(right)# 测试示例
original_array [64, 34, 25, 12, 22, 11, 90]
sorted_array quick_sort(original_array)
print(f原始数组: {original_array})
print(f排序后的数组: {sorted_array})补充知识点 1. 随机选择基准元素为了避免在某些特殊情况下如数组已经有序快速排序的性能下降可采用随机选择基准元素的方法。这样可以使算法在不同输入数据下的性能更加稳定。以下是改进后的代码 python
import randomdef quick_sort_random_pivot(arr):该函数实现随机选择基准元素的快速排序算法:param arr: 待排序的列表:return: 排序后的列表if len(arr) 1:return arrelse:# 随机选择一个基准元素的索引pivot_index random.randint(0, len(arr) - 1)# 获取基准元素pivot arr[pivot_index]# 将基准元素移到数组开头arr[0], arr[pivot_index] arr[pivot_index], arr[0]# 小于等于基准的元素组成的列表left [x for x in arr[1:] if x pivot]# 大于基准的元素组成的列表right [x for x in arr[1:] if x pivot]# 递归排序左右子数组并合并结果return quick_sort_random_pivot(left) [pivot] quick_sort_random_pivot(right)original_array [64, 34, 25, 12, 22, 11, 90]
sorted_array quick_sort_random_pivot(original_array)
print(f原始数组: {original_array})
print(f排序后的数组: {sorted_array})2. 三数取中法选择基准另一种选择基准元素的方法是三数取中法即从数组的开头、中间和结尾选取三个元素然后选择这三个元素的中位数作为基准元素这样可以进一步提高算法的性能。 5. 如何判断单向链表中是否有环 要点 可以使用快慢指针的方法来判断单向链表中是否存在环。具体思路是初始化两个指针一个慢指针和一个快指针都指向链表的头节点。慢指针每次移动一步快指针每次移动两步。如果链表中存在环那么快指针最终会追上慢指针即两个指针会相遇如果链表中不存在环那么快指针会先到达链表的末尾即快指针为 None 或快指针的下一个节点为 None。 python
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef hasCycle(head):该函数用于判断单向链表中是否有环:param head: 链表的头节点:return: 如果有环返回 True否则返回 Falseslow headfast headwhile fast and fast.next:slow slow.nextfast fast.next.nextif slow fast:return Truereturn False# 创建有环链表
node1 ListNode(1)
node2 ListNode(2)
node3 ListNode(3)
node4 ListNode(4)
node1.next node2
node2.next node3
node3.next node4
node4.next node2 # 创建环print(f链表是否有环: {hasCycle(node1)})补充知识点 找到环的入口节点当快慢指针相遇后将其中一个指针重新指向链表头然后两个指针都以每次一步的速度移动再次相遇的节点即为环的入口节点。 python
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef detectCycle(head):该函数用于判断单向链表中是否有环并找到环的入口节点:param head: 链表的头节点:return: 如果有环返回环的入口节点否则返回 Noneslow headfast headhas_cycle Falsewhile fast and fast.next:slow slow.nextfast fast.next.nextif slow fast:has_cycle Truebreakif has_cycle:slow6. 常用排序算法有哪些 要点 排序算法是将一组数据按照特定顺序通常是升序或降序重新排列的方法。常见的排序算法可分为比较排序和非比较排序两大类。 比较排序通过比较元素之间的大小关系来确定它们的顺序包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序等。 非比较排序不依赖元素之间的比较来确定顺序而是利用数据的其他特性进行排序如计数排序、桶排序和基数排序。 选择排序 python
def selection_sort(arr):选择排序算法实现:param arr: 待排序的列表:return: 排序后的列表n len(arr)for i in range(n):min_index ifor j in range(i 1, n):if arr[j] arr[min_index]:min_index jarr[i], arr[min_index] arr[min_index], arr[i]return arrarr [64, 25, 12, 22, 11]
sorted_arr selection_sort(arr)
print(f原始数组: {arr})
print(f选择排序后的数组: {sorted_arr})插入排序 python
def insertion_sort(arr):插入排序算法实现:param arr: 待排序的列表:return: 排序后的列表for i in range(1, len(arr)):key arr[i]j i - 1while j 0 and key arr[j]:arr[j 1] arr[j]j - 1arr[j 1] keyreturn arrarr [64, 25, 12, 22, 11]
sorted_arr insertion_sort(arr)
print(f原始数组: {arr})
print(f插入排序后的数组: {sorted_arr})归并排序 python
def merge_sort(arr):归并排序算法实现:param arr: 待排序的列表:return: 排序后的列表if len(arr) 1:return arrmid len(arr) // 2left merge_sort(arr[:mid])right merge_sort(arr[mid:])return merge(left, right)def merge(left, right):合并两个已排序的列表:param left: 左子列表:param right: 右子列表:return: 合并后的有序列表result []i j 0while i len(left) and j len(right):if left[i] right[j]:result.append(left[i])i 1else:result.append(right[j])j 1result.extend(left[i:])result.extend(right[j:])return resultarr [64, 25, 12, 22, 11]
sorted_arr merge_sort(arr)
print(f原始数组: {arr})
print(f归并排序后的数组: {sorted_arr})堆排序 python
import heapqdef heap_sort(arr):堆排序算法实现:param arr: 待排序的列表:return: 排序后的列表heapq.heapify(arr)return [heapq.heappop(arr) for _ in range(len(arr))]arr [64, 25, 12, 22, 11]
sorted_arr heap_sort(arr)
print(f原始数组: {arr})
print(f堆排序后的数组: {sorted_arr})计数排序 python
def counting_sort(arr):计数排序算法实现:param arr: 待排序的列表元素应为非负整数:return: 排序后的列表if not arr:return arrmax_val max(arr)count [0] * (max_val 1)for num in arr:count[num] 1result []for i in range(len(count)):result.extend([i] * count[i])return resultarr [4, 2, 2, 8, 3, 3, 1]
sorted_arr counting_sort(arr)
print(f原始数组: {arr})
print(f计数排序后的数组: {sorted_arr})补充知识点 排序算法复杂度分析不同的排序算法在时间复杂度和空间复杂度上有不同的表现。冒泡排序、选择排序和插入排序适合小规模数据的排序而归并排序、快速排序和堆排序更适合大规模数据的排序。在实际应用中需要根据数据规模、数据特点和性能要求选择合适的排序算法。 排序算法稳定性排序算法的稳定性是指相等元素在排序前后的相对顺序是否保持不变。稳定的排序算法包括冒泡排序、插入排序和归并排序等不稳定的排序算法包括选择排序、快速排序和堆排序等。在某些应用场景中如对学生成绩进行排序时需要保持相同成绩学生的原始顺序此时就需要使用稳定的排序算法。 并行排序算法对于大规模数据的排序可以采用并行排序算法来提高排序效率。例如并行归并排序可以利用多核处理器的优势将数据分成多个子任务并行处理从而显著减少排序时间。 7. 如何翻转一个单链表 要点 翻转单链表可以使用迭代和递归两种方法。 迭代方法通过遍历链表依次改变节点的指针方向将当前节点的 next 指针指向前一个节点从而实现链表的翻转。需要使用三个指针prev 用于记录前一个节点curr 用于遍历当前节点next_node 用于保存当前节点的下一个节点。 递归方法先递归地翻转当前节点之后的链表然后将当前节点的 next 指针指向前一个节点最后返回新的头节点。递归方法的关键在于理解递归的终止条件和递归调用的过程。 迭代方法 python
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef reverseList(head):迭代方法翻转单链表:param head: 链表的头节点:return: 翻转后链表的头节点prev Nonecurr headwhile curr:next_node curr.nextcurr.next prevprev currcurr next_nodereturn prev# 创建链表
node1 ListNode(1)
node2 ListNode(2)
node3 ListNode(3)
node1.next node2
node2.next node3reversed_head reverseList(node1)
current reversed_head
result []
while current:result.append(current.val)current current.next
print(f翻转后的链表值: {result})递归方法 python
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef reverseList(head):递归方法翻转单链表:param head: 链表的头节点:return: 翻转后链表的头节点if not head or not head.next:return headnew_head reverseList(head.next)head.next.next headhead.next Nonereturn new_head# 创建链表
node1 ListNode(1)
node2 ListNode(2)
node3 ListNode(3)
node1.next node2
node2.next node3reversed_head reverseList(node1)
current reversed_head
result []
while current:result.append(current.val)current current.next
print(f翻转后的链表值: {result})补充知识点 1. 部分翻转链表实现只翻转链表中指定区间的节点。可以先找到需要翻转的区间的起始节点和结束节点然后使用迭代或递归方法翻转该区间的节点最后将翻转后的区间与原链表的其他部分连接起来。 python
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef reverseBetween(head, left, right):if not head or left right:return headdummy ListNode(0)dummy.next headpre dummyfor _ in range(left - 1):pre pre.nextcur pre.nextfor _ in range(right - left):next_node cur.nextcur.next next_node.nextnext_node.next pre.nextpre.next next_nodereturn dummy.next# 创建链表
node1 ListNode(1)
node2 ListNode(2)
node3 ListNode(3)
node4 ListNode(4)
node5 ListNode(5)
node1.next node2
node2.next node3
node3.next node4
node4.next node5reversed_head reverseBetween(node1, 2, 4)
current reversed_head
result []
while current:result.append(current.val)current current.next
print(f部分翻转后的链表值: {result})2. 翻转双向链表对于双向链表除了要改变节点的 next 指针还需要改变 prev 指针。可以使用类似迭代的方法依次交换每个节点的 next 和 prev 指针。 8. 青蛙跳台阶问题一只青蛙要跳上 n 层高的台阶一次能跳一级也可以跳两级请问这只青蛙有多少种跳上这个 n 层台阶的方法 要点 这是一个典型的动态规划问题本质上是斐波那契数列问题。设 f(n) 表示跳上 n 层台阶的方法数。 当 n 1 时只有一种跳法即一次跳一级所以 f(1) 1。 当 n 2 时有两种跳法一次跳两级或分两次每次跳一级所以 f(2) 2。 当 n 2 时青蛙最后一步要么是从 n - 1 级台阶跳一级上来要么是从 n - 2 级台阶跳两级上来。因此f(n) f(n - 1) f(n - 2)。 python
def climbStairs(n):计算青蛙跳上 n 层台阶的方法数:param n: 台阶的层数:return: 跳上 n 层台阶的方法数if n 1:return 1if n 2:return 2a, b 1, 2for i in range(3, n 1):a, b b, a breturn bn 5
print(f青蛙跳上 {n} 层台阶的方法数: {climbStairs(n)})补充知识点 1. 青蛙一次可跳多级台阶若青蛙一次可以跳 1 级、2 级、...、m 级台阶可通过动态规划的思想推导出更通用的递推公式。设 f(n) 表示跳上 n 层台阶的方法数则有
python
def climbStairsMultiSteps(n, m):dp [0] * (n 1)dp[0] 1for i in range(1, n 1):for j in range(1, min(i, m) 1):dp[i] dp[i - j]return dp[n]n 5
m 3
print(f青蛙一次可跳 1 到 {m} 级台阶跳上 {n} 层台阶的方法数: {climbStairsMultiSteps(n, m)})2. 带有障碍物的台阶问题在台阶上设置障碍物青蛙不能跳到有障碍物的台阶上需要对算法进行相应调整。可以使用一个数组来标记每个台阶是否有障碍物然后在动态规划的过程中跳过有障碍物的台阶。 python
def climbStairsWithObstacles(obstacles):n len(obstacles)dp [0] * nif obstacles[0] 0:dp[0] 1for i in range(1, n):if obstacles[i] 0:if i 1:dp[i] dp[i - 1]else:dp[i] dp[i - 1] dp[i - 2]return dp[n - 1]obstacles [0, 0, 1, 0, 0]
print(f带有障碍物的台阶问题跳上最后一级台阶的方法数: {climbStairsWithObstacles(obstacles)})9. 如何求两数之和 要点 给定一个整数数组 nums 和一个目标值 target要求找出数组中两个数的和等于目标值的两个数的索引。可以使用哈希表来解决这个问题具体思路如下 遍历数组对于每个元素 num计算 target - num。 检查 target - num 是否在哈希表中。如果存在则返回这两个数的索引。 如果 target - num 不在哈希表中将当前元素 num 及其索引存入哈希表。 python
def twoSum(nums, target):找出数组中两数之和等于目标值的两个数的索引:param nums: 整数数组:param target: 目标值:return: 两个数的索引列表num_dict {}for i, num in enumerate(nums):complement target - numif complement in num_dict:return [num_dict[complement], i]num_dict[num] ireturn []nums [2, 7, 11, 15]
target 9
result twoSum(nums, target)
print(f数组 {nums} 中两数之和等于 {target} 的两个数的索引: {result})补充知识点 1. 三数之和问题找出数组中三个数的和等于目标值的所有不重复组合。可以先对数组进行排序然后固定一个数再使用双指针法在剩余的数组中寻找另外两个数使得它们的和等于目标值减去固定的数。 python
def threeSum(nums):nums.sort()result []n len(nums)for i in range(n - 2):if i 0 and nums[i] nums[i - 1]:continueleft, right i 1, n - 1while left right:total nums[i] nums[left] nums[right]if total 0:left 1elif total 0:right - 1else:result.append([nums[i], nums[left], nums[right]])while left right and nums[left] nums[left 1]:left 1while left right and nums[right] nums[right - 1]:right - 1left 1right - 1return resultnums [-1, 0, 1, 2, -1, -4]
print(f数组 {nums} 中三数之和等于 0 的所有不重复组合: {threeSum(nums)})2. 两数之和的变体如找出两数之和最接近目标值的组合。可以先对数组进行排序然后使用双指针法遍历数组记录两数之和与目标值的最小差值以及对应的组合。 10. 如何搜索旋转排序数组 要点 问题背景原本升序排列的数组在某个未知点进行了旋转例如 [0, 1, 2, 4, 5, 6, 7] 可能变为 [4, 5, 6, 7, 0, 1, 2]。要在这样的旋转排序数组中查找目标值 target若存在则返回其索引不存在则返回 -1。 算法核心采用二分查找算法。由于数组旋转后部分有序需要根据中间元素与左右边界元素的大小关系判断哪部分是有序的再结合目标值是否在有序部分内来缩小搜索范围。 python
def search(nums, target):在旋转排序数组中搜索目标值:param nums: 旋转排序数组:param target: 目标值:return: 目标值的索引若不存在则返回 -1left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] target:return mid# 判断左半部分是否有序if nums[left] nums[mid]:# 目标值在左半部分有序区间内if nums[left] target nums[mid]:right mid - 1else:left mid 1# 左半部分无序则右半部分有序else:# 目标值在右半部分有序区间内if nums[mid] target nums[right]:left mid 1else:right mid - 1return -1nums [4, 5, 6, 7, 0, 1, 2]
target 0
print(f数组 {nums} 中目标值 {target} 的索引为: {search(nums, target)})补充知识点 1. 处理重复元素当数组中存在重复元素时原有的二分查找逻辑可能会失效。例如 [1, 3, 1, 1, 1] 这样的数组在判断哪部分有序时会出现歧义。可以在每次比较时当遇到边界元素和中间元素相等的情况将边界指针向内移动一位继续进行二分查找。 python
def search_with_duplicates(nums, target):left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] target:return mid# 处理重复元素当左边界和中间元素相等时左指针右移if nums[left] nums[mid]:left 1# 判断左半部分是否有序elif nums[left] nums[mid]:if nums[left] target nums[mid]:right mid - 1else:left mid 1# 左半部分无序则右半部分有序else:if nums[mid] target nums[right]:left mid 1else:right mid - 1return -1nums [1, 3, 1, 1, 1]
target 3
print(f含重复元素的数组 {nums} 中目标值 {target} 的索引为: {search_with_duplicates(nums, target)})2. 查找旋转点除了查找目标值还可以进一步找出数组的旋转点即数组中最小元素的索引。可以使用二分查找当中间元素大于右边界元素时说明旋转点在右半部分当中间元素小于左边界元素时说明旋转点在左半部分当中间元素既不大于右边界元素也不小于左边界元素时说明数组是有序的旋转点就是左边界元素。 python
def find_rotation_point(nums):left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] nums[right]:left mid 1else:right midreturn leftnums [4, 5, 6, 7, 0, 1, 2]
print(f数组 {nums} 的旋转点索引为: {find_rotation_point(nums)})友情提示本文已经整理成文档可以到如下链接免积分下载阅读
https://download.csdn.net/download/ylfhpy/90436291
