การค้นหา: Linear และ Binary
การหาค่าค่าหนึ่ง
- งานทั่วไปคือการ ค้นหา: มีค่าอยู่ใน array หรือไม่ และอยู่ที่ ตำแหน่ง ไหน?
- คำตอบทั่วไปคือ index ที่เราพบมัน, หรือ
-1ถ้ามันไม่ได้อยู่ที่นั่น - เราเรียนวิธีการสองแบบ: linear search (ใช้ได้กับ array ใดๆ) และ binary search (ต้องใช้ array ที่ เรียงลำดับแล้ว แต่เร็วมาก)
การค้นหาแบบเชิงเส้น
- ดูแต่ละรายการตั้งแต่ index
0ไปจนถึงปลายสุด - หากรายการเท่ากับเป้าหมาย ให้กลับคืน index ของมันทันที
- หากลูปจบโดยไม่พบสิ่งที่ตรงกัน ให้กลับคืน
-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
}
}
Linear search เร็วแค่ไหน?
- ในกรณีแย่ที่สุด (ค่านั้นอยู่ในสุดท้ายหรือไม่มีอยู่เลย) มันจะตรวจสอบ ทุก รายการ
- สำหรับรายการขนาด
nจะใช้การตรวจสอบสูงสุดnครั้ง เราเรียกนี่ว่าเวลาแบบ linear - สำหรับ array ขนาดเล็กนั้นถือว่าใช้ได้เลย แต่สำหรับ array ที่เรียงลำดับ ขนาดใหญ่ เราสามารถทำได้ดีกว่านี้
Binary search ต้องใช้ array ที่เรียงลำดับแล้ว
- Binary search ใช้ได้เฉพาะเมื่ออาร์เรย์ ถูกเรียงลำดับแล้ว (จากน้อยไปมาก)
- มันตรวจสอบรายการ ตรงกลาง จากนั้นทิ้ง array ครึ่งหนึ่ง ในแต่ละขั้นตอน
- วิธีนี้เร็วกว่ามาก: รายการหนึ่งล้านรายการใช้เวลาตรวจสอบประมาณ 20 ครั้ง ไม่ใช่หนึ่งล้านครั้ง
ความคิดเรื่อง Binary search
- รักษาขอบเขตสองจุด:
low(เริ่มต้น) และhigh(สิ้นสุด) - ดูที่ middle index
mid = (low + high) / 2 - หาก
a[mid]เท่ากับเป้าหมาย ให้กลับคืนmid - หาก
a[mid]น้อยเกินไป เป้าหมายต้องอยู่ทาง ขวา ดังนั้นตั้งค่าlow = mid + 1 - หาก
a[mid]มากเกินไป เป้าหมายต้องอยู่ทาง ซ้าย ดังนั้นตั้งค่าhigh = mid - 1 - หยุดเมื่อ
lowผ่านhigh; แล้วค่าไม่อยู่ตรงนั้น ให้กลับค่า-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
}
}
เมื่อค่าไม่พบ
- ทั้งสองการค้นหาคืนค่า
-1เมื่อเป้าหมายไม่อยู่ใน array - สำหรับ binary search ลูปจะจบเมื่อ
low > high— ขอบเขตได้ข้ามกันไปแล้ว ไม่มีที่เหลือให้ค้นหา - จัดการกรณี
-1เสมอในโค้ดที่เรียกการค้นหา
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
}
}
ข้อผิดพลาดที่พบบ่อย
- Binary search ต้องใช้ array ที่ เรียงลำดับแล้ว
- Linear search คือ O(n); binary คือ O(log n)
ลองดูเลย
- Each task เติม skeleton class ไว้ล่วงหน้า — เขียนโค้ดของคุณ ภายใน main, หรือเติมเต็ม method ที่แสดง
- ใช้ Check answer เพื่อ compile โค้ดของคุณพร้อมทดสอบด้วย test ที่กำหนดและดูผลลัพธ์ รักษาโครงสร้าง class และ method ตามที่แสดงในไฟล์เริ่มต้น
- โค้ดของคุณ compile และ run บน server, ดังนั้นแม้การ run ครั้งแรกก็เร็ว
การค้นหาเชิงเส้นเทียบกับ binary search
Binary search หักครึ่งช่วงในแต่ละขั้นตอน — ตรวจสอบน้อยลงมาก.
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม linearSearch(int[] a, int target) ให้สมบูรณ์. กลับคืน ดัชนี ของ item แรกที่เท่ากับ target, หรือ -1 ถ้ามันไม่อยู่ใน array. ตรวจสอบ items จาก index 0 ขึ้นไป.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม binarySearch(int[] a, int target) สำหรับ sorted array. ใช้ low/high bounds และตรวจสอบค่าตรงกลางในแต่ละขั้นตอน. กลับคืน index ของ target, หรือ -1 ถ้ามันหาย.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม countOccurrences(int[] a, int target) ที่กลับคืนว่ามี target ปรากฏกี่ครั้งใน a (linear scan). กลับคืน 0 ถ้ามันไม่เคยปรากฏ.
คลิก Run เพื่อดูผลลัพธ์ที่นี่