Searching: linear and binary
วิธีการค้นหาสองแบบ
- การค้นหา หมายความว่าหาว่าค่าอยู่ที่ไหนในอาร์เรย์ (หรือบอกว่าไม่มีอยู่)
- Linear search ตรวจสอบทุกรายการทีละตัว ใช้งานได้กับอาร์เรย์ทุกชนิด
- Binary search เร็วกว่ามากแต่ต้องการให้อาเรย์ถูก เรียงลำดับ ก่อน
การค้นหาแบบเชิงเส้น
- เดินจากดัชนี
0ไปยังn - 1โดยเปรียบเทียบแต่ละรายการกับเป้าหมาย - คืนค่าดัชนีทันทีที่พบ ถ้าถึงจุดสิ้นสุด ให้คืนค่า
-1 - สำหรับอาเรย์ที่มี
nรายการ วิธีนี้จะตรวจสอบสูงสุดถึงnรายการ
ทำไมการจัดเรียงจึงทำให้ binary search เป็นไปได้
- ถ้าอาเรย์ถูก เรียงลำดับ คุณสามารถกระโดดไปตรง กลาง แล้วเปรียบเทียบได้
- ถ้าค่าตรงกลางเล็กเกินไป เป้าหมายต้องอยู่ในครึ่งขวา; ถ้าใหญ่เกินไป อยู่ครึ่งซ้าย
- แต่ละขั้นตอนจะทิ้งอาเรย์ออก ครึ่ง หนึ่ง จึงเร็วมาก (ประมาณ
log2(n)ขั้นตอน)
low, high, mid
- รักษาสองขอบเขต:
low(เริ่มต้น) และhigh(สิ้นสุด) ค่าตรงกลางคือmid = low + (high - low) / 2 - ถ้า
a[mid]เป็นเป้าหมาย ให้คืนค่าmid. ถ้าa[mid] < target, ย้ายlow = mid + 1; มิฉะนั้นhigh = mid - 1 - หยุดเมื่อ
low > high— เป้าหมายไม่มีอยู่ ดังนั้นคืนค่า-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;
}
ข้อผิดพลาดที่พบบ่อย
- Binary search ต้องใช้ array ที่ เรียงลำดับแล้ว
- Linear search ตรวจสอบแต่ละองค์ประกอบตามลำดับ
ลองดูเลย
- สำหรับ Binary Search ให้สมมติว่าอาร์เรย์ถูกเรียงลำดับไว้แล้ว ใช้
low,highและmid - คืนค่า
-1เมื่อไม่พบค่านั้น อย่า เขียนmain— ตัวตรวจสอบจะสร้างให้
การค้นหาเชิงเส้นเทียบกับ binary search
Binary search halves the range each step.
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
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 ไม่ใช่ write a main.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
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 ไม่ใช่ write a main.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
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 ไม่ใช่ write a main.
คลิก Run เพื่อดูผลลัพธ์ที่นี่