Làm thế nào để bạn tạo một tìm kiếm nhị phân trong python?

Trong bài đăng hôm nay, chúng ta sẽ tìm hiểu hai cách khác nhau để tạo tìm kiếm nhị phân trong Python – sử dụng đệ quy và sử dụng vòng lặp

low = 0 (index of the first element)
high = 9 (index of the last element)

Mục lục

Tìm kiếm nhị phân là gì?

Đầu tiên, hãy thảo luận về tìm kiếm nhị phân là gì

Tìm kiếm nhị phân là một thuật toán hiệu quả để tìm một phần tử trong danh sách SORTED. Nếu phần tử được tìm thấy, chúng tôi trả về chỉ mục của phần tử trong danh sách

Giả sử chúng ta có một danh sách được sắp xếp theo thứ tự tăng dần

Để thực hiện tìm kiếm nhị phân, trước tiên chúng ta so sánh mục tiêu với phần tử ở giữa danh sách

Nếu mục tiêu bằng phần tử ở giữa, chúng tôi đã tìm thấy phần tử và chỉ có thể trả về chỉ mục của phần tử đó

Ngược lại, nếu đích không bằng phần tử ở giữa, ta cần chia danh sách thành 2 nửa (không tính phần tử ở giữa)

Nếu mục tiêu lớn hơn phần tử ở giữa, chúng tôi sẽ tìm kiếm nó ở nửa trên trong các bước tiếp theo

Ngược lại, nếu mục tiêu nhỏ hơn phần tử ở giữa, chúng tôi sẽ tìm kiếm nó ở nửa dưới

Chúng tôi tiếp tục chia danh sách thành các nửa nhỏ hơn cho đến khi cuối cùng chúng tôi tìm thấy phần tử mà chúng tôi muốn

Thí dụ

Hãy xem một ví dụ về cách hoạt động của tìm kiếm nhị phân

Giả sử chúng ta có danh sách

nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]

và chúng tôi muốn tìm mục tiêu 7

Để làm điều đó bằng tìm kiếm nhị phân, chúng ta cần theo dõi ba vị trí. Hãy gọi họ.

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Lúc bắt đầu,

low = 0 (index of the first element)
high = 9 (index of the last element)

Để tìm chỉ số của phần tử ở giữa, chúng ta sử dụng công thức

middle = (high + low)/2

Nếu

low = 0 (index of the first element)
high = 9 (index of the last element)

Trong ví dụ của chúng tôi,

Bây giờ, chúng ta cần so sánh mục tiêu với

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Vì mục tiêu (7) lớn hơn

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

middle = (high + low)/2

Để bỏ qua nửa dưới, chúng tôi cập nhật giá trị của

low = 0 (index of the first element)
high = 9 (index of the last element)

Sau đó, chúng tôi tiến hành tính toán

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Đây là một minh họa đồ họa về cách thức hoạt động của nó

Tại sao tìm kiếm nhị phân hiệu quả hơn?

Nói chung, tìm kiếm nhị phân được coi là một thuật toán tìm kiếm rất hiệu quả. Chẳng hạn như trong ví dụ trên, chúng ta chỉ mất 3 bước để tìm mục tiêu

Ngược lại, nếu chúng ta thực hiện tìm kiếm tuyến tính (i. e. lặp lại từng phần tử danh sách cho đến khi chúng tôi tìm thấy mục tiêu của mình), chúng tôi sẽ cần 9 bước (vì mục tiêu là số thứ 9 trong danh sách)

Tìm kiếm nhị phân có hiệu quả cao vì chúng tôi loại bỏ một nửa danh sách ở mỗi bước và chỉ tập trung vào một nửa nơi có thể có mục tiêu

Đối với một danh sách có

middle = (high + low)/2

Ngược lại, tìm kiếm tuyến tính sẽ yêu cầu tối đa __6_______4 bước

Như vậy, tìm kiếm nhị phân được coi là hiệu quả hơn nhiều so với tìm kiếm tuyến tính.

Nhược điểm của tìm kiếm nhị phân

Mặc dù tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuyến tính nhưng nó cũng có một số nhược điểm

Đầu tiên, danh sách phải được sắp xếp để thuật toán hoạt động. Nếu danh sách không được sắp xếp, chúng tôi không thể xác định xem mục tiêu nằm ở nửa dưới hay nửa trên chỉ bằng cách so sánh nó với phần tử ở giữa

Ngoài ra, tìm kiếm nhị phân có thể không nhất thiết cho chúng ta lần xuất hiện đầu tiên của mục tiêu mà chúng ta muốn. Chẳng hạn, giả sử

middle = (high + low)/2

middle = (high + low)/2

Cách thực hiện Tìm kiếm nhị phân trong Python bằng vòng lặp while

Bây giờ chúng ta đã biết cách thức hoạt động của tìm kiếm nhị phân, hãy xem xét hai cách tiếp cận mà chúng ta có thể sử dụng để thực hiện tìm kiếm

Cách tiếp cận đầu tiên là sử dụng vòng lặp

low = 0 (index of the first element)
high = 9 (index of the last element)

def binarySearch(nums, target):

    low = 0
    high = len(nums) - 1
    middle = 0
  
    while low <= high:  
        middle = (high + low) // 2  
        
        # target equals nums[middle], return middle (index of target)
        if target == nums[middle]: 
            return middle

        # Take the upper half 
        elif target > nums[middle]: 
            low = middle + 1
  
        # Take the lower half
        else: 
            high = middle - 1
  
    # If we reach this line, target is not present in nums
    return -1

Trong đoạn mã trên, trước tiên chúng ta khai báo một hàm có tên là

middle = (high + low)/2

Bên trong hàm, chúng ta khai báo và khởi tạo 3 biến tên là

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Tiếp theo, chúng ta sử dụng vòng lặp

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Trong vòng lặp, nếu chúng ta tìm thấy trường hợp

middle 
= (0+9)/2 
= 4.5 
= 4 (rounded down)

low = 0 (index of the first element)
high = 9 (index of the last element)

Mặt khác, chúng tôi cập nhật giá trị của

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Chúng tôi tiếp tục làm điều này trong khi

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Nếu chúng tôi đạt đến trường hợp

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Do đó, chúng tôi thoát khỏi vòng lặp

low = 0 (index of the first element)
high = 9 (index of the last element)

Cách thực hiện Tìm kiếm nhị phân trong Python bằng Đệ quy

Ngoài việc sử dụng vòng lặp

low = 0 (index of the first element)
high = 9 (index of the last element)

def binarySearchRec(nums, target, low, high):

    if low <= high:  
        middle = (high + low) // 2

        # target equals nums[middle], return middle (index of target)
        if target == nums[middle]: 
            return middle
        
        # Take the upper half 
        elif target > nums[middle]: 
            return binarySearchRec(nums, target, middle + 1, high)
  
        # Take the lower half
        else: 
            return binarySearchRec(nums, target, low, middle - 1)
        
    # If we reach this line, target is not present in nums
    else:
        return -1

Ở đây, chúng ta định nghĩa một hàm có tên là

def binarySearch(nums, target):

    low = 0
    high = len(nums) - 1
    middle = 0
  
    while low <= high:  
        middle = (high + low) // 2  
        
        # target equals nums[middle], return middle (index of target)
        if target == nums[middle]: 
            return middle

        # Take the upper half 
        elif target > nums[middle]: 
            low = middle + 1
  
        # Take the lower half
        else: 
            high = middle - 1
  
    # If we reach this line, target is not present in nums
    return -1

low = 0 (index of the first element)
high = 9 (index of the last element)

middle 
= (0+9)/2 
= 4.5 
= 4 (rounded down)

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

Bên trong hàm, thay vì cập nhật rõ ràng các giá trị của

low = 0 (index of the first element)
high = 9 (index of the last element)

low = 0 (index of the first element)
high = 9 (index of the last element)

def binarySearch(nums, target):

    low = 0
    high = len(nums) - 1
    middle = 0
  
    while low <= high:  
        middle = (high + low) // 2  
        
        # target equals nums[middle], return middle (index of target)
        if target == nums[middle]: 
            return middle

        # Take the upper half 
        elif target > nums[middle]: 
            low = middle + 1
  
        # Take the lower half
        else: 
            high = middle - 1
  
    # If we reach this line, target is not present in nums
    return -1

Chẳng hạn, giả sử chúng ta gọi hàm bằng mã bên dưới

target = 7
nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]

print(binarySearchRec(nums, target, 0, len(nums) - 1))

Khi chúng ta gọi hàm

def binarySearch(nums, target):

    low = 0
    high = len(nums) - 1
    middle = 0
  
    while low <= high:  
        middle = (high + low) // 2  
        
        # target equals nums[middle], return middle (index of target)
        if target == nums[middle]: 
            return middle

        # Take the upper half 
        elif target > nums[middle]: 
            low = middle + 1
  
        # Take the lower half
        else: 
            high = middle - 1
  
    # If we reach this line, target is not present in nums
    return -1

def binarySearchRec(nums, target, low, high):

    if low <= high:  
        middle = (high + low) // 2

        # target equals nums[middle], return middle (index of target)
        if target == nums[middle]: 
            return middle
        
        # Take the upper half 
        elif target > nums[middle]: 
            return binarySearchRec(nums, target, middle + 1, high)
  
        # Take the lower half
        else: 
            return binarySearchRec(nums, target, low, middle - 1)
        
    # If we reach this line, target is not present in nums
    else:
        return -1

hàm và tính giá trị của

low = 0 (index of the first element)
high = 9 (index of the last element)

def binarySearch(nums, target):

    low = 0
    high = len(nums) - 1
    middle = 0
  
    while low <= high:  
        middle = (high + low) // 2  
        
        # target equals nums[middle], return middle (index of target)
        if target == nums[middle]: 
            return middle

        # Take the upper half 
        elif target > nums[middle]: 
            low = middle + 1
  
        # Take the lower half
        else: 
            high = middle - 1
  
    # If we reach this line, target is not present in nums
    return -1

middle
= (0+9)//2
= 4

hàm so sánh

middle 
= (0+9)/2 
= 4.5 
= 4 (rounded down)

low = 0 (index of the first element)
high = 9 (index of the last element)

Vì 7 lớn hơn 2 (i. e.

target = 7
nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]

print(binarySearchRec(nums, target, 0, len(nums) - 1))

target = 7
nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]

print(binarySearchRec(nums, target, 0, len(nums) - 1))

Điều này dẫn đến việc thực hiện

target = 7
nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]

print(binarySearchRec(nums, target, 0, len(nums) - 1))

Bên trong việc thực hiện

target = 7
nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]

print(binarySearchRec(nums, target, 0, len(nums) - 1))

chúng tôi tính toán lại giá trị của

low = 0 (index of the first element)
high = 9 (index of the last element)

middle 
= (5+9)//2 
= 7

và

middle 
= (0+9)/2 
= 4.5 
= 4 (rounded down)

target = 7
nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]

print(binarySearchRec(nums, target, 0, len(nums) - 1))

target = 7
nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]

print(binarySearchRec(nums, target, 0, len(nums) - 1))

Điều này dẫn đến việc thực hiện

middle
= (0+9)//2
= 4

Bên trong việc thực hiện

middle
= (0+9)//2
= 4

chúng tôi tính toán lại giá trị của

low = 0 (index of the first element)
high = 9 (index of the last element)

middle
= (8+9)//2 
= 8

Vì 7 bằng

middle
= (0+9)//2
= 4

Chúng tôi không còn gọi hàm

def binarySearch(nums, target):

    low = 0
    high = len(nums) - 1
    middle = 0
  
    while low <= high:  
        middle = (high + low) // 2  
        
        # target equals nums[middle], return middle (index of target)
        if target == nums[middle]: 
            return middle

        # Take the upper half 
        elif target > nums[middle]: 
            low = middle + 1
  
        # Take the lower half
        else: 
            high = middle - 1
  
    # If we reach this line, target is not present in nums
    return -1

middle
= (0+9)//2
= 4

low = 0 (index of the first element)
high = 9 (index of the last element)

Tìm kiếm nhị phân được thực hiện như thế nào trong Python?

Có tìm kiếm nhị phân trong Python không?