Searching: linear and binary
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Trang này cần trình duyệt gần đây (hỗ trợ SharedArrayBuffer). Vui lòng cập nhật Chrome, Edge, Firefox hoặc Safari lên phiên bản mới nhất.
English
Two ways to search
- Searching means finding where a value is in an array (or saying it is not there).
- Linear search checks every item one by one. It works on any array.
- Binary search is much faster but needs the array to be sorted first.
Tiếng Việt
Hai cách tìm kiếm
- Tìm kiếm nghĩa là tìm xem giá trị nằm ở đâu trong mảng (hoặc khẳng định nó không tồn tại).
- Tìm kiếm tuyến tính kiểm tra từng mục một. Nó hoạt động trên mọi mảng.
- Tìm kiếm nhị phân nhanh hơn nhiều nhưng cần mảng phải được sắp xếp trước.
English
Linear search
- Walk from index
0ton - 1, comparing each item to the target. - Return the index the moment you find it. If you reach the end, return
-1. - For an array of
nitems, this looks at up tonof them.
Tiếng Việt
Tìm kiếm tuyến tính
- Duyệt từ chỉ số
0đếnn - 1, so sánh từng mục với giá trị mục tiêu. - Trả về chỉ số ngay khi bạn tìm thấy. Nếu bạn đi hết, hãy trả về
-1. - Đối với mảng có
nmục, phương pháp này sẽ kiểm tra tối đanmục.
English
Why sorting enables binary search
- If the array is sorted, you can jump to the middle and compare.
- If the middle is too small, the target must be in the right half; if too big, the left half.
- Each step throws away half the array, so it is very fast (about
log2(n)steps).
Tiếng Việt
Tại sao sắp xếp lại hỗ trợ tìm kiếm nhị phân
- Nếu mảng được sắp xếp, bạn có thể nhảy đến giữa và so sánh.
- Nếu giá trị giữa quá nhỏ, mục tiêu chắc chắn nằm ở nửa bên phải; nếu quá lớn, nằm ở nửa bên trái.
- Mỗi bước loại bỏ nửa mảng, do đó nó rất nhanh (khoảng
log2(n)bước).
English
low, high, mid
- Keep two bounds:
low(start) andhigh(end). The middle ismid = low + (high - low) / 2. - If
a[mid]is the target, returnmid. Ifa[mid] < target, movelow = mid + 1; elsehigh = mid - 1. - Stop when
low > high— the target is not there, so return-1.
Tiếng Việt
low, high, mid
- Giữ hai cận:
low(bắt đầu) vàhigh(kết thúc). Giá trị giữa làmid = low + (high - low) / 2. - Nếu
a[mid]là mục tiêu, trả vềmid. Nếu làa[mid] < target, di chuyểnlow = mid + 1; ngược lại di chuyểnhigh = mid - 1. - Dừng lại khi
low > high— mục tiêu không có ở đây, nên trả về-1.
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
English
Common mistakes
- Binary search needs a sorted array.
- Linear search checks each element in turn.
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 kiểm tra từng phần tử theo thứ tự.
English
Now you try
- For binary search, assume the array is already sorted. Use
low,high, andmid. - Return
-1when the value is not found. Do not write amain— the checker provides one.
Tiếng Việt
Bây giờ bạn thử
- Đối với tìm kiếm nhị phân, giả sử mảng đã được sắp xếp. Sử dụng
low,highvàmid. - Trả về
-1khi không tìm thấy giá trị. Không viết mộtmain— trình kiểm tra sẽ tự làm điều đó.
Explore · Khám phá
Linear vs binary search
Binary search halves the range each step.
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do not write a main.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do not write a main.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do not write a main.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.