Searching · การค้นหา (Searching)
Searching a list
- Searching means finding whether a value is in a list, and where.
- The usual answer is the index of the value, or
-1if it is missing. - Two classic methods are linear search and binary search.
การค้นหาในลิสต์
- การค้นหา หมายความว่าค้นหาค่าว่าอยู่ในลิสต์หรือไม่ และอยู่ที่ตำแหน่งใด
- คำตอบทั่วไปคือ ดัชนี ของค่า หรือ
-1ถ้าค่านั้นไม่มีอยู่ - วิธีคลาสสิกสองวิธีคือการค้นหาแบบเชิงเส้นและการค้นหาแบบทวิภาค
Linear search
- Check each item in turn, from the start.
- Stop as soon as you find a match.
- It works on any list, sorted or not.
การค้นหาแบบเชิงเส้น
- ตรวจสอบแต่ละรายการทีละรายการ เริ่มจากต้น
- หยุดทันทีเมื่อพบสิ่งที่ตรงกัน
- ใช้ได้กับ ทุก ลิสต์ ทั้งที่เรียงลำดับแล้วหรือไม่
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Binary search
- Binary search needs a sorted list.
- Look at the middle item. If it is the target, stop.
- If the target is smaller, search the left half; if bigger, the right half.
การค้นหาแบบทวิภาค
- การค้นหาแบบทวิภาคต้องการลิสต์ที่ เรียงลำดับแล้ว
- ดูที่รายการ กลาง หากเป็นเป้าหมายให้หยุด
- หากเป้าหมายมีค่าน้อยกว่า ให้ค้นหาครึ่งซ้าย; หากมากกว่า ให้ค้นหาครึ่งขวา
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
Compare them
- Linear search may check every item — slow for a long list.
- Binary search throws away half the list each step, so it is much faster.
- But binary search only works if the data is already sorted.
เปรียบเทียบกัน
- การค้นหาแบบเชิงเส้นอาจตรวจสอบ ทุก รายการ — ช้าสำหรับลิสต์ที่ยาว
- การค้นหาแบบทวิภาคตัด ครึ่ง ของลิสต์ทิ้งในแต่ละขั้นตอน จึงเร็วมาก
- แต่การค้นหาแบบทวิภาคใช้ได้ก็ต่อเมื่อข้อมูลถูก เรียงลำดับ แล้วเท่านั้น
In Cambridge pseudocode
- Note
DIVis whole-number division (Python's//).
ใน伪代码 Cambridge
- หมายเหตุ
DIVเป็นการหารจำนวนเต็ม (Python ใช้//)
// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← mid
ELSE
IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDIF
ENDWHILE
Common mistakes
- Binary search needs a sorted list; it halves the range each step.
- Linear search works on any list but is slower.
ข้อผิดพลาดที่พบบ่อย
- การค้นหาแบบทวิภาคต้องการลิสต์ที่ เรียงลำดับแล้ว; มันลดช่วงลงครึ่งหนึ่งในแต่ละขั้นตอน
- การค้นหาแบบเชิงเส้นใช้ได้กับลิสต์ทุกอย่างแต่ช้ากว่า
Now you try
- Return the index of the value, or
-1when it is not found. - Press Check answer to test your code.
ลองดูเลย
- คืนค่า ดัชนี ของค่า หรือ
-1เมื่อไม่พบ - กด Check answer เพื่อทดสอบโค้ดของคุณ
Linear vs binary search · การค้นหาเชิงเส้นเทียบกับ binary search
Binary search halves the list each step — far fewer comparisons. · Binary search แบ่งครึ่ง list ในแต่ละขั้นตอน — ลดจำนวนการเปรียบเทียบอย่างมาก
Write linear_search(items, target) that returns the index of target in items, or -1 if it is not there. Check the items one by one. · เขียน linear_search(items, target) ที่ คืนค่า ดัชนีของ target ใน items, หรือ -1 หากไม่มีอยู่. ตรวจสอบรายการทีละตัว
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write binary_search(items, target) for a sorted list. Return the index of target, or -1 if it is missing. Halve the range each step. · เขียน binary_search(items, target) สำหรับ sorted list. Return ดัชนีของ target, หรือ -1 หากหายไปได้. แบ่งช่วงระยะทางครึ่งหนึ่งในแต่ละขั้นตอน
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write first_negative(items) that scans the list and returns the index of the first number less than 0, or -1 if there are none. · เขียน first_negative(items) ที่สแกน list และ คืนค่า ดัชนีของตัวเลขตัวแรกที่น้อยกว่า 0, หรือ -1 หากไม่มีเลย
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่