Tìm kiếm

Tìm kiếm là quá trình thuật toán để tìm một mục cụ thể trong một tập hợp các mục. Tìm kiếm thường trả lời là đúng hoặc sai vì mục đó có tồn tại hay không. Một số phương pháp tìm kiếm phổ biến: tìm kiếm tuần tự, tìm kiếm nhị phân, tìm kiếm cây nhị phân, tìm kiếm băm

Tìm kiếm nhị phân

Tìm kiếm nhị phân còn được gọi là tìm kiếm nhị phân. Ưu điểm của nó là ít thời gian so sánh hơn, tốc độ tìm kiếm nhanh và hiệu suất trung bình tốt; nhược điểm của nó là bảng cần tra cứu bắt buộc phải là một danh sách có thứ tự và khó chèn và xóa. Vì vậy, phương pháp tìm kiếm nhị phân thích hợp để tìm kiếm các danh sách có thứ tự thường xuyên không thay đổi thường xuyên. Trước hết, giả sử các phần tử trong bảng được sắp xếp theo thứ tự tăng dần, so sánh khóa của bản ghi ở vị trí giữa của bảng với khóa tìm kiếm, nếu hai phần tử bằng nhau thì việc tìm kiếm thành công; ngược lại, sử dụng bản ghi vị trí giữa để chia bảng thành bảng con thứ nhất và thứ hai, nếu Khóa của bản ghi vị trí giữa lớn hơn khóa tìm kiếm thì bảng con trước được tìm kiếm thêm, ngược lại bảng con sau được tìm kiếm thêm. Lặp lại quá trình trên cho đến khi tìm thấy một bản ghi đáp ứng các điều kiện và tìm kiếm thành công, hoặc cho đến khi bảng con không tồn tại thì lúc này tìm kiếm không thành công.

Binary_search_into_array

Thực hiện tìm kiếm nhị phân

(Triển khai không đệ quy)

def binary_search(alist, item):
      first = 0
      last = len(alist)-1
      while first<=last:
          midpoint = (first + last)/2
          if alist[midpoint] == item:
              return True
          elif item < alist[midpoint]:
              last = midpoint-1
          else:
              first = midpoint+1
    return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

(Triển khai đệ quy)

def binary_search(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint]==item:
          return True
        else:
          if item<alist[midpoint]:
            return binary_search(alist[:midpoint],item)
          else:
            return binary_search(alist[midpoint+1:],item)

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

thời gian phức tạp

• Độ phức tạp thời gian tối ưu: O (1)

• Độ phức tạp về thời gian tệ nhất: O (logn)