การค้นหาข้อมูลที่เรียงแล้ว
การค้นหาแบบทวิภาค
การค้นหาข้อมูลที่เรียงแล้ว เป็นบทเรียน Go Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Go Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Go Academy มีบทเรียนทั้งหมด 4 บทเรียน
เหตุใดจึงค้นหาข้อมูลที่เรียงลำดับแล้ว
เมื่อสไลซ์เรียงลำดับแล้ว คุณจะค้นหาองค์ประกอบได้เร็วขึ้นมากด้วยการค้นหาแบบไบนารีแทนการตรวจสอบทุกรายการ
แพ็กเกจ sort ของ Go มีตัวช่วยค้นหาที่ทำงานในเวลาแบบลอการิทึม
เชิงเส้นเทียบกับไบนารี
การค้นหาแบบเชิงเส้นจะตรวจสอบแต่ละองค์ประกอบทีละรายการ (O(n)) ส่วนการค้นหาแบบไบนารีจะลดช่วงการค้นหาลงครึ่งหนึ่งในแต่ละขั้นตอน (O(log n)) แต่ข้อมูลจะต้องเรียงลำดับไว้ก่อน
sort.SearchInts
sort.SearchInts จะค้นหาดัชนีที่มีค่าอยู่ หรือดัชนีที่ควรแทรกค่าเพื่อให้สไลซ์ยังคงเรียงลำดับอยู่ สไลซ์จะต้องเรียงจากน้อยไปมากไว้แล้ว
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7, 9}
i := sort.SearchInts(nums, 5)
fmt.Println("index:", i)
}ยืนยันการจับคู่
SearchInts จะส่งกลับดัชนีแม้ไม่มีค่านั้นอยู่ โดยดัชนีดังกล่าวคือจุดแทรก ควรยืนยันผลเสมอด้วยการตรวจสอบ i < len(s) && s[i] == target
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7}
target := 4
i := sort.SearchInts(nums, target)
found := i < len(nums) && nums[i] == target
fmt.Println("index:", i, "found:", found)
}จุดแทรก
เมื่อไม่มีค่าที่ค้นหา ดัชนีที่ส่งกลับมาคือตำแหน่งที่ควรแทรกค่านั้นพอดี เพื่อให้ข้อมูลยังเรียงลำดับอยู่ ในตัวอย่างนี้ ค่า 4 ควรอยู่ที่ดัชนี 2
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7}
i := sort.SearchInts(nums, 4)
fmt.Println("insert 4 at index:", i)
}SearchStrings
sort.SearchStrings ทำงานเช่นเดียวกันกับสไลซ์สตริงที่เรียงลำดับแล้ว
package main
import (
"fmt"
"sort"
)
func main() {
words := []string{"apple", "cherry", "mango"}
i := sort.SearchStrings(words, "cherry")
fmt.Println("index:", i)
}sort.Search ทั่วไป
sort.Search เป็นแกนหลักที่ยืดหยุ่น คุณส่งความยาวและฟังก์ชัน f ที่ให้ผลเป็น false ก่อนแล้วจึงเป็น true จากนั้นฟังก์ชันจะส่งกลับดัชนีที่น้อยที่สุดซึ่ง f ให้ผลเป็น true
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{2, 4, 6, 8, 10}
i := sort.Search(len(nums), func(i int) bool {
return nums[i] >= 6
})
fmt.Println("first >= 6 at index:", i)
}ค้นหาองค์ประกอบแรกที่มากกว่า
เนื่องจาก sort.Search ค้นหาขอบเขตที่เงื่อนไขเปลี่ยนเป็น true จึงเหมาะอย่างยิ่งกับการค้นหา เช่น ค่าค่าแรกที่มากกว่าเกณฑ์ที่กำหนด
package main
import (
"fmt"
"sort"
)
func main() {
scores := []int{10, 20, 30, 40}
i := sort.Search(len(scores), func(i int) bool {
return scores[i] > 25
})
fmt.Println("first > 25:", scores[i])
}ต้องเรียงลำดับก่อน
การค้นหาแบบไบนารีอาศัยลำดับ หากสไลซ์ไม่ได้เรียงลำดับ ผลลัพธ์จะไม่มีความหมาย ควรเรียงลำดับก่อนค้นหาเสมอ
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{9, 1, 5, 3}
sort.Ints(nums)
i := sort.SearchInts(nums, 5)
fmt.Println(nums, "-> index of 5:", i)
}ข้อได้เปรียบด้านประสิทธิภาพ
สำหรับสไลซ์ที่มีองค์ประกอบหนึ่งล้านรายการ การค้นหาแบบเชิงเส้นอาจต้องตรวจสอบหนึ่งล้านรายการ แต่การค้นหาแบบไบนารีตรวจสอบประมาณ 20 รายการ ต้นทุนของการเรียงลำดับเพียงครั้งเดียวจะคุ้มค่าเมื่อมีการค้นหาหลายครั้ง
เลือกตัวช่วยค้นหาที่เหมาะสม
สรุป:
sort.SearchInts/SearchStrings/SearchFloat64s- สำหรับสไลซ์ที่มีชนิดระบุไว้sort.Search- สำหรับเงื่อนไขแบบกำหนดเองบนข้อมูลใด ๆ ที่เข้าถึงด้วยดัชนีได้
ตรวจสอบอย่างรวดเร็ว
คุณเรียกใช้ sort.SearchInts(s, 4) กับสไลซ์ที่เรียงลำดับแล้วแต่ไม่มีค่า 4 อยู่ ฟังก์ชันจะส่งกลับอะไร
ทบทวน
การค้นหาข้อมูลที่เรียงลำดับแล้วด้วยการค้นหาแบบไบนารี:
- ต้องเรียงลำดับข้อมูลก่อน
- ตัวช่วยจะส่งกลับดัชนีหรือจุดแทรก
- ยืนยันการจับคู่ด้วยการตรวจสอบความเท่ากัน
sort.Searchรองรับเงื่อนไขแบบกำหนดเอง
คำถามที่พบบ่อย
บทเรียน “การค้นหาข้อมูลที่เรียงแล้ว” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การค้นหาข้อมูลที่เรียงแล้ว” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Go Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Go Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การค้นหาข้อมูลที่เรียงแล้ว”
การค้นหาแบบทวิภาค คุณปฏิบัติ Go Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Go Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Go Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “การค้นหาข้อมูลที่เรียงแล้ว” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Go Academy นี้ได้ไหม
ได้ บทเรียน Go Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การเรียงลำดับสไลซ์
- ลำดับการเรียงแบบกำหนดเอง
- การค้นหาข้อมูลที่เรียงแล้ว
- การเรียงลำดับแบบคงเสถียรภาพ