[Python Code] Python Binary Search(Tìm kiếm nhị phân)

Python Binary Search.

Tìm kiếm nhị phân là một trong những thuật toán tìm kiếm rất cơ bản và thường được sử dụng rất phổ biến

Với đầu vào là một mảng dữ liệu được sắp xếp tuần tự theo một tính chất nào đó.

Ví dụ tăng dần, giảm dần, hoặc bắt đầu từ một vị trí a thì có một đặc điểm chung.

BinarySearch sẽ được ứng dụng để tìm kiếm một phần tử trong một mảng dữ liệu như ở trên.

Code python binary search

Ví dụ một danh sách các phần tử có tính chất sắp xếp theo chiều tăng hoặc giảm các giá trị

# Phattrienphanmem123az.com
import math
import os

# find x in data_list
# start: first index
# end : last index
def BinarySearch(data_list, start, end, x):
    if end >= start:
        mid = start + (end - start)//2
        if data_list[mid] == x:
            return mid
        elif data_list[mid] > x:
            return BinarySearch(data_list, start, mid-1, x)
        else:
            return BinarySearch(data_list, mid+1, end, x)
    else:
        return -1


def main():
    data_list = [1, 2, 3, 5, 9, 10, 15, 19]
    x = 9
    start = 0
    end = len(data_list)-1

    ret = BinarySearch(data_list, start, end, x)
    if ret == -1:
        print("Not Existed")
    else:
        print("Found Postion:" + str(ret))
    return 0

if __name__ == "__main__":
    main()

 

Ouput:

Found Postion:4

 

Một ví dụ khác. Cho một tập các dữ liệu từ vị trí 0 đến vị trí end = 6

Bắt  đầu từ vị trí x nào đó, dữ liệu đó bị thay đổi giá trị (từ 0 thay đổi thành 1)

Tìm vị trí x đó.

#phattrienphanmem123az.com
import math
import os

class TData:
    def __init__(self, x):
        self.x = x


def BinarySearch(data_list, start, end, x):
    if end > start:
        mid = start + (end - start)//2
        if data_list[mid].x == x:
            return BinarySearch(data_list, start, mid, x)
        else:
            return BinarySearch(data_list, mid+1, end, x)
    elif end == start:
        return start
    else:
        return -1


def main():
    data_list = list()
    data1 = TData(0)
    data2 = TData(0)
    data3 = TData(1)
    data4 = TData(1)
    data5 = TData(1)
    data6 = TData(1)

    data_list.append(data1)
    data_list.append(data2)
    data_list.append(data3)
    data_list.append(data4)
    data_list.append(data5)
    data_list.append(data6)

    x = 1
    start = 0
    end = len(data_list)-1
    # right: ret = 3
    ret = BinarySearch(data_list, start, end, x)
    if ret == -1:
        print("Not Existed")
    else:
        print("Found Postion:" + str(ret))
    return 0


if __name__ == "__main__":
    main()

Ok.