Algorithms: searching
หน้านี้ต้องใช้เบราว์เซอร์ล่าสุด (รองรับ SharedArrayBuffer) กรุณาอัปเดต Chrome, Edge, Firefox หรือ Safari เป็นเวอร์ชันล่าสุด
สิ่งที่เราจะทำ
- อัลกอริทึม คือรายการขั้นตอนที่ชัดเจนเพื่อแก้ปัญหา
- งานที่พบบ่อยมากคือ การค้นหา: หาว่าค่าหนึ่งอยู่ในตำแหน่งใดของรายการ
- เราจะเรียนอัลกอริทึมสองแบบ: การค้นหาเชิงเส้น และ การค้นหาแบบแบ่งครึ่ง
การค้นหาแบบเชิงเส้น
- ตรวจสอบรายการ ทีละรายการ จากต้นจนจบ
- หากพบค่าที่ต้องการ ให้ส่งกลับ ดัชนี (ตำแหน่ง) ของค่านั้น
- หากไปถึงท้ายรายการโดยไม่พบเลย ให้ส่ง
-1
English
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
ทำไมรายการที่มีลำดับจึงช่วยได้
- การค้นหาเชิงเส้นใช้กับ รายการใดก็ได้ แม้จะเป็นรายการที่ไม่เป็นระเบียบก็ตาม
- แต่ถ้ารายการมี ลำดับ (เล็กไปหาใหญ่) เราจะทำได้เร็วขึ้นมาก
- การค้นหาแบบแบ่งครึ่ง ใช้ลำดับที่มีอยู่เพื่อข้ามครึ่งหนึ่งของรายการในครั้งหนึ่ง
การค้นหาแบบทวิภาค
- ดูที่รายการ ตรงกลาง
- ถ้าตรงกับเป้าหมาย คุณก็เสร็จสิ้นแล้ว
- ถ้าเป้าหมาย น้อยกว่า ให้ค้นหาครึ่ง ซ้าย; ถ้า มากกว่า ให้ค้นหาครึ่ง ขวา ทำซ้ำ
English
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
การรวมแนวคิดเข้าด้วยกัน
- การค้นหา รวม โครงสร้างพื้นฐานสามส่วนที่คุณรู้จักอยู่แล้วเข้าด้วยกัน
- การเรียงลำดับ: ทำขั้นตอนตามลำดับ การเลือก:
if/elif/else - การทำซ้ำ: ลูป (
forหรือwhile) ทำการตรวจสอบซ้ำ
In AP CSP pseudocode
- ข้อสอบจะเขียนลูปและการตรวจสอบเช่นนี้
FOR EACHเข้าถึงทุกรายการ;IFเลือก;REPEAT UNTILลูปจนกว่าเงื่อนไขจะเป็นจริง
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
ข้อผิดพลาดที่พบบ่อย
- การค้นหาแบบทวิภาคต้องการลิสต์ที่ เรียงลำดับแล้ว
- การค้นหาเชิงเส้นตรวจสอบแต่ละรายการตามลำดับ
ลองดูเลย
- แต่ละโจทย์กำหนดชื่อขั้นตอนและสิ่งที่ต้องส่งกลับ
- กด Check answer เพื่อทดสอบโค้ดของคุณ
สำรวจ
การค้นหาในรายการ
Binary search ต้องการรายการที่ เรียงลำดับ แต่เร็วกว่า linear มาก
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เขียน linear_search(lst, target) คืนค่า ดัชนี ของ target ใน lst หรือ -1 หากไม่พบ ตรวจสอบทีละรายการ
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เขียน binary_search(sorted_lst, target) สำหรับลิสต์ที่เรียงจากน้อยไปมาก กลับค่า ดัชนี ของ target หรือ -1 ดูค่าตรงกลางและตัดช่วงการค้นหาลงครึ่งหนึ่งทุกครั้ง
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เขียน contains(lst, target) ที่คืนค่า True หาก target อยู่ใน lst มิฉะนั้นคืนค่า False สามารถใช้ linear search ซ้ำและเปรียบเทียบกับ -1
คลิก Run เพื่อดูผลลัพธ์ที่นี่