Algorithms: searching
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · หน้านี้ต้องใช้เบราว์เซอร์ล่าสุด (รองรับ SharedArrayBuffer) กรุณาอัปเดต Chrome, Edge, Firefox หรือ Safari เป็นเวอร์ชันล่าสุด
English
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
ไทย
สิ่งที่เราจะทำ
- อัลกอริทึม คือรายการขั้นตอนที่ชัดเจนเพื่อแก้ปัญหา
- งานที่พบบ่อยมากคือ การค้นหา: หาว่าค่าหนึ่งอยู่ในตำแหน่งใดของรายการ
- เราจะเรียนอัลกอริทึมสองแบบ: การค้นหาเชิงเส้น และ การค้นหาแบบแบ่งครึ่ง
English
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
ไทย
การค้นหาแบบเชิงเส้น
- ตรวจสอบรายการ ทีละรายการ จากต้นจนจบ
- หากพบค่าที่ต้องการ ให้ส่งกลับ ดัชนี (ตำแหน่ง) ของค่านั้น
- หากไปถึงท้ายรายการโดยไม่พบเลย ให้ส่ง
-1
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
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
ไทย
ทำไมรายการที่มีลำดับจึงช่วยได้
- การค้นหาเชิงเส้นใช้กับ รายการใดก็ได้ แม้จะเป็นรายการที่ไม่เป็นระเบียบก็ตาม
- แต่ถ้ารายการมี ลำดับ (เล็กไปหาใหญ่) เราจะทำได้เร็วขึ้นมาก
- การค้นหาแบบแบ่งครึ่ง ใช้ลำดับที่มีอยู่เพื่อข้ามครึ่งหนึ่งของรายการในครั้งหนึ่ง
English
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
ไทย
การค้นหาแบบทวิภาค
- ดูที่รายการ ตรงกลาง
- ถ้าตรงกับเป้าหมาย คุณก็เสร็จสิ้นแล้ว
- ถ้าเป้าหมาย น้อยกว่า ให้ค้นหาครึ่ง ซ้าย; ถ้า มากกว่า ให้ค้นหาครึ่ง ขวา ทำซ้ำ
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))
English
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
ไทย
การรวมแนวคิดเข้าด้วยกัน
- การค้นหา รวม โครงสร้างพื้นฐานสามส่วนที่คุณรู้จักอยู่แล้วเข้าด้วยกัน
- การเรียงลำดับ: ทำขั้นตอนตามลำดับ การเลือก:
if/elif/else - การทำซ้ำ: ลูป (
forหรือwhile) ทำการตรวจสอบซ้ำ
English
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
ไทย
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)
}
English
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
ไทย
ข้อผิดพลาดที่พบบ่อย
- การค้นหาแบบทวิภาคต้องการลิสต์ที่ เรียงลำดับแล้ว
- การค้นหาเชิงเส้นตรวจสอบแต่ละรายการตามลำดับ
English
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
ไทย
ลองดูเลย
- แต่ละโจทย์กำหนดชื่อขั้นตอนและสิ่งที่ต้องส่งกลับ
- กด Check answer เพื่อทดสอบโค้ดของคุณ
Explore · สำรวจ
Searching a list · การค้นหาในรายการ
Binary search needs a sorted list but is far faster than linear. · Binary search ต้องการรายการที่ เรียงลำดับ แต่เร็วกว่า linear มาก
Write linear_search(lst, target). Return the index of target in lst, or -1 if it is not there. Check items one by one. · เขียน linear_search(lst, target) คืนค่า index ของ target ใน lst หรือ -1 หากไม่พบ ตรวจสอบทีละรายการ
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time. · เขียน binary_search(sorted_lst, target) สำหรับรายการที่เรียง从小到大 Return index ของ target หรือ -1 ดูตรงกลางและตัดครึ่งการค้นหาทุกครั้ง
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write contains(lst, target) that returns True if target is in lst, else False. You may reuse linear search and compare the result to -1. · เขียน contains(lst, target) ที่คืนค่า True หาก target อยู่ใน lst มิฉะนั้นคืนค่า False สามารถใช้ linear search ซ้ำและเปรียบเทียบกับ -1
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่