Tìm kiếm nhị phân trong PHP (đệ quy)

Thuật toán tìm kiếm nhị phân là một thuật toán dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp. Thuật toán hoạt động như sau: Trong mỗi bước, so sánh phần tử cần tìm với phần tử nằm ở chính giữa danh sách, nếu hai phần tử bằng nhau thì phép tìm kiếm thành công và thuật toán kết thúc, nếu chúng không bằng nhau thì tùy vào phần tử nào lớn hơn, thuật toán lặp lại bước so sánh trên với nửa đầu hoặc nửa sau của danh sách, vì số lượng phần tử trong danh sách cần xem xét giảm đi một nửa sau mỗi bước, nên thời gian thực thi của thuật toán là hàm lôgarit.

Thuật toán:

 - Đầu vào:

• $gt - giá trị cần tìm
• $mang - mảng sổ chứa các phần tử
• $dau, $cuoi - chỉ số đầu cuối của mảng

 - Đầu ra:

• Trả về true nếu tìm thấy, false nếu không tìm thấy

Chạy thuật toán:

Bước 1: gán $dau = 0, $cuoi = số phần tử mảng - 1

Bước 2: so sánh $dau, $cuoi , nếu $dau > $cuoi , trả về false

Bước 3: Tính vị trí phần tử ở giữa, $giua = ($dau + $cuoi) / 2, sau đó so sánh với $gt, có 3 trường hợp:

• Nếu $gt bằng với phần tử ở giữa, trả về true
• Nếu $gt nhỏ hơn phần tử ở giữa, $cuoi  = $giua - 1, quay lại bước 2
• Nếu $gt lớn hơn phần tử ở giữa, $dau = $giua + 1, quay lại bước 2

Cài đặt thuật toán:

Trong function, mình có thêm dòng kiểm tra, nếu $gt bằng giá trị của phần tử đầu/cuối thì trả về true, có thể nó sẽ tìm nhanh hơn.

Lưu ý, bạn cần sắp xếp mảng theo tứ tự từ nhỏ đến lơn, hoặc ngược lại để tìm kiếm, đây cũng là mặt hạn chế của thuật toán.

Để sắp xếp mảng trong PHP, dùng hàm sort() :

hải long