อัลกอริทึมการค้นหา
แนะนำใหม่| English | ความหมาย |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | การค้นหา |
| linear search/ˈlɪnɪə sɜːtʃ/ | การค้นหาแบบเชิงเส้น |
| binary search/ˈbaɪnəri sɜːtʃ/ | การค้นหาแบบแบ่งครึ่ง |
| sorted/ˈsɔːtɪd/ | เรียงลำดับแล้ว |
การหาค่า
- Searching คือการหาเป้าหมายในชุดข้อมูล
- สองอัลกอริทึมมาตรฐาน: linear search และ binary search
- ทั้งคู่คืนค่า index ที่เป้าหมายอยู่ — หรือสัญญาณ "not found" (มักจะเป็น
-1) - คุณจะใช้ตัวไหนขึ้นอยู่กับว่าข้อมูลถูก sorted หรือไม่
การค้นหาเชิงเส้น
- ตรวจสอบแต่ละองค์ประกอบ จากต้น, ทีละตัว จนกว่าจะเจอเป้าหมาย
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- ใช้ได้กับ any array — sorted หรือไม่ก็ได้
- กรณีแย่สุด: มันดูทุก every องค์ประกอบ (
nchecks)
การค้นหาแบบทวิภาค
- ต้องการ sorted array. ดูองค์ประกอบ middle ทุกครั้ง
- ถ้า middle คือเป้าหมาย เสร็จแล้ว ถ้าเป้าหมาย smaller, ค้นหา left half; ถ้า larger, right half
- แต่ละขั้นตอน halves ช่วงที่เหลือในการค้นหา
- เร็วกว่ามากบน large sorted arrays — ประมาณ
log₂ nchecks, ไม่ใช่n
ทำไม binary search ถึงเร็ว
- การค้นหาเชิงเส้นของรายการหนึ่งล้านรายการ: อาจต้องตรวจสอบสูงสุดหนึ่งล้านครั้ง
- การค้นหาแบบทวิภาคของรายการหนึ่งล้านรายการที่ เรียงลำดับแล้ว: ตรวจสอบประมาณ 20 ครั้ง
- ข้อควรระวัง: array ต้องถูก sorted อยู่แล้ว
- Halving ซ้ำๆ คือแนวคิดหลักเบื้องหลัง
O(log n)
Binary search ใช้ได้เฉพาะกับ SORTED array — รัน它对 unsorted data จะได้คำตอบผิด它还比较到 middle 并丢弃 half 的 range 每步; linear search 从 start 比较并只 drop one element.如果你不确定数据是否已排序,你必须使用 linear search (或先排序)
Binary search for 7 in [1, 3, 5, 7, 9]:
- Middle is
5(index 2). 7 > 5, so search the right half. - Right half is
[7, 9]; middle is7. Found at index 3. - ตรวจสอบเพียงสองครั้งแทนสี่ครั้ง — ช่วงในการค้นหาจะ减半ทุกครั้งที่ลดลง
การค้นหาเชิงเส้น ตรวจสอบองค์ประกอบตั้งแต่ต้น (ใช้ได้กับ arreglo ใดๆ ตรวจสอบสูงสุด n ครั้ง) การค้นหาแบบทวิภาค ต้องใช้ arreglo ที่ เรียงลำดับแล้ว เปรียบเทียบกับ ค่าตรงกลาง และ 减半 ช่วงในการค้นหาทุกขั้นตอน (ตรวจสอบประมาณ log₂ n ครั้ง) ทั้งสองวิธีจะคืนค่าดัชนีที่พบ หรือสัญญาณ "ไม่พบ" เช่น -1
การค้นหาเชิงเส้นเทียบกับ binary search
Binary search ลดช่วงข้อมูลที่เรียงแล้วลงครึ่งหนึ่งในแต่ละขั้นตอน
การค้นหาเชิงเส้น...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Linear = จากต้นจนจบ; ใช้ได้กับ数组ทุกชนิด
Binary search ต้องการให้数组เป็น...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Binary search ใช้งานได้ดีเฉพาะข้อมูลที่เรียงลำดับแล้วเท่านั้น
แต่ละขั้นตอนของ binary search...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
เปรียบเทียบค่ากับตรงกลางและเก็บไว้เพียงครึ่งหนึ่ง
Binary search ใน [1,3,5,7,9] เพื่อหาค่า 7: มีการเปรียบเทียบกี่ครั้ง (ตรงกลางทุกครั้ง)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
เปรียบเทียบกับ 5, แล้วเปรียบเทียบกับ 7 — เปรียบเทียบทั้งหมด 2 ครั้ง
Binary search ให้ผลลัพธ์ที่ถูกต้องบน数组ที่ไม่ได้เรียงลำดับ
Difficulty 1/5 · 100 coins + a small bonus on first completion today
มันพึ่งพาการเรียงลำดับ; ข้อมูลที่ไม่ได้เรียงทำให้มันล้มเหลว
จับคู่การค้นหากับคุณสมบัติของแต่ละประเภท
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Linear เป็นวิธีทั่วไปแต่ช้ากว่า; Binary search เร็วกว่าแต่ต้องมีการเรียงลำดับ