Tìm kiếm nhị phân

Tìm một giá trong list một triệu phần tử bằng cách duyệt từ đầu, xấu nhất phải so một triệu lần. Nếu list đã sắp xếp, chỉ cần khoảng 20 lần so.

Khái niệm

🌓 Tìm kiếm nhị phân (binary search): trên dãy đã sắp xếp, so với phần tử ở giữa rồi bỏ đi nửa không thể chứa giá trị cần tìm, lặp lại tới khi thấy hoặc hết dãy.

Mỗi bước bỏ một nửa, nên 1.000.000 phần tử chỉ cần khoảng 20 bước, vì 2 mũ 20 là 1.048.576. Đó là O(log n): gấp đôi dữ liệu chỉ thêm một bước.

Ví dụ

int[] prices =
{
    3000, 5000, 7000, 12000, 25000, 350000, 450000
};
Console.WriteLine(Find(prices, 12000));   // 3
Console.WriteLine(Find(prices, 8000));    // -1

int Find(int[] items, int target)
{
    int low = 0;
    int high = items.Length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (items[mid] == target)
        {
            return mid;
        }
        if (items[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

low và high là hai đầu của đoạn còn phải tìm. Ban đầu là cả array.
mid là vị trí giữa. / giữa hai số nguyên bỏ phần lẻ, như bài Toán tử và ép kiểu của khoá C# Core.
Giá ở giữa nhỏ hơn giá cần tìm thì bỏ nửa trái, lớn hơn thì bỏ nửa phải.
Đoạn còn lại rỗng (low > high) mà vẫn chưa thấy thì trả -1.

▶ Mô phỏng: Tìm 25000 trong 7 giá

int[] prices = { 3000, 5000, 7000, 12000, 25000, 350000, 450000 };
Console.WriteLine(Find(prices, 25000));

int Find(int[] items, int target)
{
    int low = 0;
    int high = items.Length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (items[mid] == target)
        {
            return mid;
        }
        if (items[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

Xem từng bước

Đoạn còn phải tìm ban đầu là cả dãy: low = 0, high = 6.
Bước 1: đoạn 0..6, ô giữa là mid = (0 + 6) / 2 = 3, giá 12000.
12000 < 25000: 25000 chỉ có thể nằm bên phải, bỏ nửa trái. low = mid + 1 = 4.
Bước 2: đoạn 4..6, ô giữa là mid = (4 + 6) / 2 = 5, giá 350000.
350000 > 25000: 25000 chỉ có thể nằm bên trái, bỏ nửa phải. high = mid - 1 = 4.
Bước 3: đoạn 4..4, ô giữa là mid = (4 + 4) / 2 = 4, giá 25000.
25000 == 25000: thấy ở vị trí 4 sau 3 bước.
find trả về 4. Dãy 7 phần tử mà chỉ mất 3 bước: mỗi bước bỏ một nửa, O(log n).

.NET có sẵn Array.BinarySearch(array, x) và list.BinarySearch(x). Không thấy thì chúng trả về một số âm.

Thử ngay

Chép Find thành CountSteps, thêm biến đếm số bước, rồi tìm trong một triệu số:

int[] big = new int[1000000];
for (int i = 0; i < big.Length; i++)
{
    big[i] = i + 1;
}
Console.WriteLine(CountSteps(big, 500000));
Console.WriteLine(CountSteps(big, 1000000));

int CountSteps(int[] items, int target)
{
    int steps = 0;
    int low = 0;
    int high = items.Length - 1;
    while (low <= high)
    {
        steps++;
        int mid = (low + high) / 2;
        if (items[mid] == target)
        {
            return steps;
        }
        if (items[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return steps;
}

Đoán trước khi chạy: tìm 500000 và tìm 1000000 mất bao nhiêu bước?

Xem kết quả

1
20

500000 nằm đúng giữa nên thấy ngay ở bước đầu. 1000000 nằm cuối, gần như trường hợp xấu nhất, cũng chỉ mất 20 bước. Duyệt từ đầu thì mất một triệu bước.

Lỗi hay gặp

Tìm nhị phân trên dãy chưa sắp xếp. Chương trình không báo lỗi, chỉ trả về kết quả sai, vì bỏ nửa dãy chỉ đúng khi dãy có thứ tự. Array.Sort sắp xếp array tăng dần.

// SAI — 3000 có trong dãy nhưng trả về -1
int[] prices = { 12000, 3000, 450000, 5000, 7000 };
Console.WriteLine(Array.BinarySearch(prices, 3000));

// ĐÚNG — sắp xếp trước rồi mới tìm
int[] prices = { 12000, 3000, 450000, 5000, 7000 };
Array.Sort(prices);
Console.WriteLine(Array.BinarySearch(prices, 3000));

Tóm tắt

Tìm nhị phân so với phần tử giữa rồi bỏ một nửa dãy mỗi bước.
O(log n): một triệu phần tử chỉ khoảng 20 bước.
Chỉ đúng trên dãy đã sắp xếp.
.NET có Array.BinarySearch và List<T>.BinarySearch, không thấy thì trả số âm.

Tìm một giá trong list một triệu phần tử bằng cách duyệt từ đầu, xấu nhất phải so một triệu lần. Nếu list đã sắp xếp, chỉ cần khoảng 20 lần so.

Khái niệm

Mỗi bước bỏ một nửa, nên 1.000.000 phần tử chỉ cần khoảng 20 bước, vì 2 mũ 20 là 1.048.576. Đó là O(log n): gấp đôi dữ liệu chỉ thêm một bước.

Ví dụ

int[] prices =
{
    3000, 5000, 7000, 12000, 25000, 350000, 450000
};
Console.WriteLine(Find(prices, 12000));   // 3
Console.WriteLine(Find(prices, 8000));    // -1

int Find(int[] items, int target)
{
    int low = 0;
    int high = items.Length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (items[mid] == target)
        {
            return mid;
        }
        if (items[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

low và high là hai đầu của đoạn còn phải tìm. Ban đầu là cả array.
mid là vị trí giữa. / giữa hai số nguyên bỏ phần lẻ, như bài Toán tử và ép kiểu của khoá C# Core.
Giá ở giữa nhỏ hơn giá cần tìm thì bỏ nửa trái, lớn hơn thì bỏ nửa phải.
Đoạn còn lại rỗng (low > high) mà vẫn chưa thấy thì trả -1.

▶ Mô phỏng: Tìm 25000 trong 7 giá

int[] prices = { 3000, 5000, 7000, 12000, 25000, 350000, 450000 };
Console.WriteLine(Find(prices, 25000));

int Find(int[] items, int target)
{
    int low = 0;
    int high = items.Length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (items[mid] == target)
        {
            return mid;
        }
        if (items[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

Xem từng bước

Đoạn còn phải tìm ban đầu là cả dãy: low = 0, high = 6.
Bước 1: đoạn 0..6, ô giữa là mid = (0 + 6) / 2 = 3, giá 12000.
12000 < 25000: 25000 chỉ có thể nằm bên phải, bỏ nửa trái. low = mid + 1 = 4.
Bước 2: đoạn 4..6, ô giữa là mid = (4 + 6) / 2 = 5, giá 350000.
350000 > 25000: 25000 chỉ có thể nằm bên trái, bỏ nửa phải. high = mid - 1 = 4.
Bước 3: đoạn 4..4, ô giữa là mid = (4 + 4) / 2 = 4, giá 25000.
25000 == 25000: thấy ở vị trí 4 sau 3 bước.
find trả về 4. Dãy 7 phần tử mà chỉ mất 3 bước: mỗi bước bỏ một nửa, O(log n).

.NET có sẵn Array.BinarySearch(array, x) và list.BinarySearch(x). Không thấy thì chúng trả về một số âm.

Thử ngay

Chép Find thành CountSteps, thêm biến đếm số bước, rồi tìm trong một triệu số:

int[] big = new int[1000000];
for (int i = 0; i < big.Length; i++)
{
    big[i] = i + 1;
}
Console.WriteLine(CountSteps(big, 500000));
Console.WriteLine(CountSteps(big, 1000000));

int CountSteps(int[] items, int target)
{
    int steps = 0;
    int low = 0;
    int high = items.Length - 1;
    while (low <= high)
    {
        steps++;
        int mid = (low + high) / 2;
        if (items[mid] == target)
        {
            return steps;
        }
        if (items[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return steps;
}

Đoán trước khi chạy: tìm 500000 và tìm 1000000 mất bao nhiêu bước?

Xem kết quả

1
20

Lỗi hay gặp

// SAI — 3000 có trong dãy nhưng trả về -1
int[] prices = { 12000, 3000, 450000, 5000, 7000 };
Console.WriteLine(Array.BinarySearch(prices, 3000));

// ĐÚNG — sắp xếp trước rồi mới tìm
int[] prices = { 12000, 3000, 450000, 5000, 7000 };
Array.Sort(prices);
Console.WriteLine(Array.BinarySearch(prices, 3000));

Tóm tắt

Tìm nhị phân so với phần tử giữa rồi bỏ một nửa dãy mỗi bước.
O(log n): một triệu phần tử chỉ khoảng 20 bước.
Chỉ đúng trên dãy đã sắp xếp.
.NET có Array.BinarySearch và List<T>.BinarySearch, không thấy thì trả số âm.

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Bình luận

Tìm kiếm nhị phân

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Bình luận