Searching: linear and binary · ⁨Tìm kiếm: tuyến tính và nhị phân⁩

English

Finding a value

A common job is to search: is a value in an array, and where?
The usual answer is the index where we found it, or -1 if it is not there.
We learn two ways: linear search (works on any array) and binary search (needs a sorted array, but is much faster).

Tiếng Việt

Tìm kiếm một giá trị

Một công việc phổ biến là tìm kiếm: liệu có giá trị đó trong mảng không, và nằm ở đâu?
Đáp án thường là chỉ số nơi tìm thấy, hoặc -1 nếu không tìm thấy.
Chúng ta học hai cách: tìm kiếm tuyến tính (làm việc với mọi mảng) và tìm kiếm nhị phân (cần mảng đã được sắp xếp, nhưng nhanh hơn nhiều).

English

Linear search

Look at each item from index 0 to the end.
If the item equals the target, return its index right away.
If the loop finishes with no match, return -1.

Tiếng Việt

Tìm kiếm tuyến tính

Xem xét từng phần tử từ chỉ số 0 trở đi.
Nếu phần tử bằng mục tiêu, trả về chỉ số của nó ngay lập tức.
Nếu vòng lặp kết thúc mà không tìm thấy, trả về -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {4, 8, 15, 16, 23};
        int target = 15;
        int found = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                found = i;
                break;       // stop early, we have it
            }
        }
        System.out.println(found);   // 2
    }
}

English

How fast is linear search?

In the worst case (the value is last, or missing) it checks every item.
For a list of n items that is up to n checks. We call this linear time.
For small arrays this is totally fine. For huge sorted arrays we can do better.

Tiếng Việt

Tìm kiếm tuyến tính nhanh thế nào?

Trong trường hợp xấu nhất (giá trị nằm cuối cùng hoặc bị thiếu), nó kiểm tra mọi phần tử.
Với danh sách n phần tử, tối đa cần n lần kiểm tra. Ta gọi đây là thời gian tuyến tính.
Đối với mảng nhỏ thì hoàn toàn ổn. Nhưng đối với mảng sắp xếp rất lớn, chúng ta có thể làm tốt hơn.

English

Binary search needs a sorted array

Binary search only works when the array is already sorted (small to large).
It checks the middle item, then throws away half the array each step.
That is much faster: a million items take about 20 checks, not a million.

Tiếng Việt

Tìm kiếm nhị phân cần mảng sắp xếp

Tìm kiếm nhị phân chỉ hoạt động khi mảng đã được sắp xếp sẵn (từ nhỏ đến lớn).
Nó kiểm tra phần tử ở giữa, rồi loại bỏ một nửa mảng ở mỗi bước.
Điều này nhanh hơn nhiều: một triệu phần tử chỉ mất khoảng 20 lần kiểm tra, chứ không phải một triệu.

English

The binary search idea

Keep two bounds: low (start) and high (end).
Look at the middle index mid = (low + high) / 2.
If a[mid] equals the target, return mid.
If a[mid] is too small, the target must be on the right, so set low = mid + 1.
If a[mid] is too big, the target must be on the left, so set high = mid - 1.
Stop when low passes high; then the value is not there, return -1.

Tiếng Việt

Ý tưởng tìm kiếm nhị phân

Giữ hai giới hạn: low (bắt đầu) và high (kết thúc).
Xem xét chỉ số giữa mid = (low + high) / 2.
Nếu a[mid] bằng mục tiêu, trả về mid.
Nếu a[mid] quá nhỏ, mục tiêu phải nằm ở phải, nên cập nhật low = mid + 1.
Nếu a[mid] quá lớn, mục tiêu phải nằm ở trái, nên cập nhật high = mid - 1.
Dừng lại khi low vượt qua high; lúc đó giá trị không tồn tại, trả về -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38};   // sorted!
        int target = 16;

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;     // go right
            } else {
                high = mid - 1;    // go left
            }
        }
        System.out.println(found);   // 4
    }
}

English

When a value is missing

Both searches return -1 when the target is not in the array.
For binary search, the loop ends when low > high — the bounds have crossed, so there is nowhere left to look.
Always handle the -1 case in code that calls a search.

Tiếng Việt

Khi giá trị bị thiếu

Cả hai phương pháp đều trả về -1 khi mục tiêu không có trong mảng.
Đối với tìm kiếm nhị phân, vòng lặp kết thúc khi low > high — các giới hạn đã cắt nhau, nên không còn vùng nào để tìm nữa.
Luôn xử lý trường hợp -1 trong mã nguồn gọi hàm tìm kiếm.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12};   // sorted
        int target = 7;            // not in the array

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(found);   // -1
    }
}

English

Common mistakes

Binary search needs a sorted array.
Linear search is O(n); binary is O(log n).

Tiếng Việt

Lỗi thường gặp

Tìm kiếm nhị phân cần mảng sắp xếp.
Tìm kiếm tuyến tính là O(n); nhị phân là O(log n).

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

Tiếng Việt

Bây giờ bạn thử

Mỗi nhiệm vụ điền sẵn khung lớp — viết mã của bạn bên trong main, hoặc hoàn thành phương thức được hiển thị.
Nhấn Chạy để biên dịch và chạy, sau đó Kiểm tra câu trả lời.
Mã của bạn được biên dịch và chạy trên máy chủ, vì vậy ngay cả lần chạy đầu tiên cũng rất nhanh.

Explore · ⁨Khám phá⁩

Linear vs binary search · ⁨Tìm kiếm tuyến tính so với tìm kiếm nhị phân⁩

Binary search halves the range each step — far fewer checks. · ⁨Tìm kiếm nhị phân chia đôi phạm vi tìm kiếm mỗi bước — giảm đáng kể số lần kiểm tra.⁩

Complete linearSearch(int[] a, int target). Return the index of the first item equal to target, or -1 if it is not in the array. Check items from index 0 upward. · ⁨Hoàn thiện linearSearch(int[] a, int target). Trả về chỉ mục của phần tử đầu tiên bằng với target, hoặc trả về -1 nếu nó không có trong mảng. Kiểm tra các phần tử từ chỉ mục 0 trở lên.⁩

public class SearchUtil {
    // Return the index of target, or -1 if not found.
    public static int linearSearch(int[] a, int target) {
        return -1;   // change this
    }
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Complete binarySearch(int[] a, int target) for a sorted array. Use low/high bounds and check the middle each step. Return the index of target, or -1 if it is missing. · ⁨Hoàn thiện binarySearch(int[] a, int target) cho mảng đã sắp xếp. Sử dụng cận low/high và kiểm tra phần tử giữa ở mỗi bước. Trả về chỉ số của target, hoặc -1 nếu không tìm thấy.⁩

public class SearchUtil {
    // Binary search on a sorted array. Return index or -1.
    public static int binarySearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        // your loop here
        return -1;
    }
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears. · ⁨Hoàn thiện countOccurrences(int[] a, int target) trả về số lần target xuất hiện trong a (dùng quét tuyến tính). Trả về 0 nếu nó chưa bao giờ xuất hiện.⁩

public class SearchUtil {
    // Count how many times target appears in a.
    public static int countOccurrences(int[] a, int target) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Searching: linear and binary · ⁨Tìm kiếm: tuyến tính và nhị phân⁩

Finding a value

Tìm kiếm một giá trị

Linear search

Tìm kiếm tuyến tính

How fast is linear search?

Tìm kiếm tuyến tính nhanh thế nào?

Binary search needs a sorted array

Tìm kiếm nhị phân cần mảng sắp xếp

The binary search idea

Ý tưởng tìm kiếm nhị phân

When a value is missing

Khi giá trị bị thiếu

Common mistakes

Lỗi thường gặp

Now you try

Bây giờ bạn thử

Linear vs binary search · ⁨Tìm kiếm tuyến tính so với tìm kiếm nhị phân⁩

Handout · ⁨Tài liệu⁩

Log in or create account · ⁨Đăng nhập hoặc tạo tài khoản⁩

Your subject · ⁨Môn học của bạn⁩

All sections · ⁨Tất cả các mục⁩

Feedback & help · ⁨Phản hồi & hỗ trợ⁩