Thuật toán tìm kiếm_Bạch Thành Long_C1019I1

Hôm nay lớp C1019I1 chúng tôi học về thuật toán tìm kiếm, là một thuật toán rất phổ biến trong bài, tôi xin lược thuật đơn gian với bạn đọc như sau.

Thuật toán tìm kiếm tuyến tính là gì?

Thuật toánn sắp xếp và thuật toán tìm kiếm

Tại sao dùng Thuật toán tìm kiếm tuyến tính?

Chúng ta cần tìm kiếm trên danh sách các dữ liệu như sách, email, cơ sở dữ liệu, file…

Dùng Thuật toán tìm kiếm tuyến tính thế nào?

Đó là lần lượt so sánh các phần tử trong danh sách với dữ liệu đang muốn tìm kiếm, từ đầu cho đến cuối.

Ví dụ

function search(array $numbers, int $needle): bool {
    $totalItems = count($numbers);

for ($i = 0; $i < $totalItems; $i++) {
if($numbers[$i] === $needle){
return TRUE;
        }
    }
return FALSE;
}

Thuật toán tìm kiếm nhị phân

là thuật toán tìm kiếm được sử dụng rất phổ biến trong thế giới lập trình. Thông thường, thuật toán tìm kiếm nhị phân sẽ có hiệu suất cao hơn rất nhiều so với tìm kiếm tuyến tính.
thuật toán tìm kiếm nhị phân đó là các phần tử phải được sắp xếp theo một trật tự nhất định.

Dùng thế nào

Đầu tiên, chúng ta chia mảng thành hai nửa theo phép toán: midIndex = startIndex + (endIndex + startIndex) / 2

Với ví dụ trên là 0 + (9 – 0)/ 2 = 4 (giá trị là 4.5). Do đó midIndex của mảng trên là 4. Chúng ta so sánh giá trị tại chỉ mục này với giá trị cần tìm.

Ví duj:

<?php

function FindNum(array $arr, $num)
{
    $low = 0;
    $high = count($arr)-1;

while ($low <= $high) {
        $mid = (int)(($high + $low) / 2);
if ($arr[$mid] < $num) {
            $mid++;
            $low = $mid;
        } else if ($arr[$mid] > $num) {
            $mid–;
            $high = $mid;
        } else {
echo “Find”;
return true;
        }
    }
echo “Not Find”;
return false;
}