1
Thuật toán tìm kiếm nhị phân hoạt động như thế nào?
0
Member447810 đã đăng:

Mọi người ai có thể giải thích giúp mình đoạn mã nguồn tìm kiếm nhị phân bên dưới hoạt động như thế nào không ạ?

int BinarySearch(int a[], int n, int x)
{
    int left = 0, right = n - 1, mid;
    do
    {
        mid = (left + right) / 2;
        if (x == a[mid])
            return mid;
        else if (x < a[mid])
            right = mid - 1;
        else
            left = mid + 1;
    } while (left <= right);

    return -1;
}

Bạn có thể mô tả rõ hơn các giá trị tham số đầu vào của hàm BinarySearch được không?

xuans2huy 02.01.2019

Hàm BinarySearch nhận vào một mảng a, có số lượng phần tử của mảng là n và giá trị cần tìm là x ạ.

Member4478 02.01.2019
thêm bình luận...
1
xuans2huy510 đã đăng:

Đầu tiên, thuật toán tìm kiếm nhị phân giả sử mảng a đầu vào là mảng đã được sắp xếp theo thứ tự tăng dần, nếu mảng a chưa được sắp xếp mà sử dụng thuật toán tìm kiếm nhị phân thì kết quả sẽ bị sai.

Ý tưởng cơ bản nhất của thuật toán tìm kiếm nhị phân là chia để trị, nói một cách đơn giản hơn là chia nhỏ mảng ra để tìm kiếm, thay vì duyệt trên toàn bộ mảng như thuật toán tìm kiếm tuần tự, thuật toán tìm kiếm nhị phân chia mảng thành những vùng nhỏ hơn và chọn lấy một vùng phù hợp để tìm kiếm trong đó thôi, bạn có thể thấy câu lệnh mid = (left + right) / 2 với mục đích để chia nhỏ mảng, nếu lần chia nhỏ mảng đầu tiên chưa tìm được phần tử cần tìm, tiếp tục chia nhỏ mảng cho đến khi không thể chia nhỏ được nữa, tức là left <= right thì dừng, lúc này có thể trả về -1 để thông báo rằng không tìm thấy phần tử đó trong mảng.

Giả sử chúng ta có một mảng a gồm các phần tử đã được sắp xếp như sau:

$$[1, 2, 3, 4, 5, 6, 7]$$

Chúng ta cần tìm phần tử 6 trong mảng?

Chia nhỏ mảng a lần 1 bằng cách tính chỉ số giữa của mảng: mid = (0 + 7) / 2 = 3. Ta có a[3] = 4, kiểm tra xem x == a[mid] hay không, tức là $6 == 4$ hay không? Không. Nhưng chúng ta biết rằng 6 > 4, vậy tức là số 6 sẽ nằm bên phải số 4, vậy có lý do gì để ta tìm kiếm bên trái mảng a nữa không? Không, ta sẽ chỉ tìm vùng bên phải a mà thôi tức là vùng có chỉ số từ mid tới right.

Vậy các câu lệnh:

else if (x < a[mid])
    right = mid - 1;
else
    left = mid + 1;

kiểm tra xem giá trị cần tìm lớn hơn hay nhỏ giá trị giữa mid, nếu lớn hơn, cập nhật lại left = mid + 1 để chỉ tìm sang bên phải, nếu nhỏ hơn, cập nhật lại right = mid - 1 để chỉ tìm sang bên trái mảng.

Qua lần chia nhỏ đầu tiên, mảng a sẽ còn:

$$[4, 5, 6, 7]$$

Tiếp tục chia nhỏ lần thứ hai, tương tự, tính chỉ số mid, a[mid] lúc này bằng 5, so sánh a[mid] với số 6, 6 vẫn lớn hơn, vậy bỏ vùng bên trái tìm kiếm sang bên phải, mảng a sau khi chia nhỏ lần thứ 2 sẽ còn:

$$[6, 7]$$

Tiếp tục chia nhỏ lần thứ ba, tính chí số mid, a[mid] = 6, so sánh a[mid] với số 6, bằng nhau, trả về đã tìm được số 6 trong mảng.

Khi không thể chia được nữa, tức là left <= right hay mảng chỉ còn 1 phần tử, mà phần tử đó lại không bằng với phần tử cần tìm, trả về -1 với ý nghĩa không tìm thấy.

đã bổ sung 5.5 năm trước bởi
xuans2huy510

Cảm ơn câu trả lời chi tiết của bạn, vậy theo mình hiểu thì giả sử chúng ta biết rằng phần tử đó tồn tại trong mảng, thì sau những lần chia nhỏ mảng, chắc chắn sẽ có trường hợp:

if (x == a[mid])
    return mid;

tức là đã tìm được, còn không thì cứ dịch sang nửa trái hoặc nửa phải của mảng dựa vào độ lớn của phần tử cần tìm, mỗi lần dịch, mảng sẽ càng nhỏ dần nhỏ dần đến khi chỉ còn duy nhất 1 phần tử và không thể chia nhỏ nữa, thuật toán dừng, kết quả là không tìm thấy.

Member4478 04.01.2019

Chính xác, trừ khi phần tử không tồn tại trong mảng, còn nếu không câu lệnh x == a[mid] sẽ xảy ra sau vài lần phân chia.

xuans2huy 04.01.2019
thêm bình luận...
Bạn đang thắc mắc? Ghi câu hỏi của bạn và đăng ở chế độ cộng đồng (?)