Searching: linear and binary
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.
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.
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).
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;
}
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ự.
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 đó.
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.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 không write a main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 không write a main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 không write a main.
Nhấn Chạy để xem kết quả ở đây.