Tìm kiếm: tuyến tính và nhị phân
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
-1nế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).
Tìm kiếm tuyến tính
- Xem xét từng phần tử từ chỉ số
0trở đ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
}
}
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
nphần tử, tối đa cầnnlầ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.
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.
Ý 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ậtlow = mid + 1. - Nếu
a[mid]quá lớn, mục tiêu phải nằm ở trái, nên cập nhậthigh = mid - 1. - Dừng lại khi
lowvượt quahigh; 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
}
}
Khi giá trị bị thiếu
- Cả hai phương pháp đều trả về
-1khi 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
-1trong 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
}
}
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).
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ị.
- Sử dụng Check answer để biên dịch mã của bạn với các bài kiểm tra được cung cấp và xem kết quả. Giữ nguyên giao diện class và phương thức được hiển thị trong file khởi tạo.
- 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.
Tìm kiếm tuyến tính so với tìm kiếm nhị phân
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.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
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
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.
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
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.
Nhấn Chạy để xem kết quả ở đây.