如何使用Python实现链表的二分查找

2023-04-11 00:00:00 查找链表如何使用

实现链表的二分查找需要满足如下几个步骤：

将链表转换为有序数组。
对有序数组进行二分查找。
根据查找结果在链表中进行定位。

具体过程如下：

1.首先，需要定义链表节点Node的数据结构，包括保存数据和指向下一个节点的指针。以字符串作为数据类型的示例代码如下：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

将链表转换为有序数组

定义一个函数，将链表转换为有序数组，代码示例如下：

def convert_to_array(head):
    arr = []
    cur = head
    while cur:
        arr.append(cur.data)
        cur = cur.next
    arr.sort() # 将数组排序
    return arr

对有序数组进行二分查找

定义一个函数，对有序数组进行二分查找，代码示例如下：

def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else: # arr[mid] > target
            right = mid - 1
    return -1 # 未找到

根据查找结果在链表中进行定位

根据二分查找的结果，在链表中进行定位，代码示例如下：

def search(head, target):
    arr = convert_to_array(head) # 将链表转为有序数组
    index = binary_search(arr, target) # 在有序数组中查找
    if index == -1: # 未找到
        return None
    # 找到目标节点
    cur = head
    for i in range(index):
        cur = cur.next
    return cur

完整代码演示如下：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def convert_to_array(head):
    arr = []
    cur = head
    while cur:
        arr.append(cur.data)
        cur = cur.next
    arr.sort() # 将数组排序
    return arr

def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else: # arr[mid] > target
            right = mid - 1
    return -1 # 未找到

def search(head, target):
    arr = convert_to_array(head) # 将链表转为有序数组
    index = binary_search(arr, target) # 在有序数组中查找
    if index == -1: # 未找到
        return None
    # 找到目标节点
    cur = head
    for i in range(index):
        cur = cur.next
    return cur

# 示例
head = Node('p')
cur = head
for c in 'idancode.com':
    node = Node(c)
    cur.next = node
    cur = cur.next

target_node = search(head, 'p')
print(target_node.data) # p

target_node = search(head, 'g')
print(target_node) # None

输出结果为：

p
None

相关文章