การค้นหาด้วยนิ้วในโครงสร้างข้อมูล

การค้นหาด้วยนิ้วบนโครงสร้างข้อมูลถูกกำหนดให้เป็นส่วนขยายของการดำเนินการค้นหาใดๆ ที่โครงสร้างรองรับ โดยที่การอ้างอิง (นิ้ว) ไปยังองค์ประกอบในโครงสร้างข้อมูลจะได้รับพร้อมกับแบบสอบถาม แม้ว่าเวลาในการค้นหาองค์ประกอบมักแสดงเป็นฟังก์ชันของจำนวนองค์ประกอบในโครงสร้างข้อมูล แต่เวลาในการค้นหาด้วยนิ้วจะถือเป็นฟังก์ชันของระยะห่างระหว่างองค์ประกอบและนิ้ว

ในชุดขององค์ประกอบ m ระยะทาง d(a, b) ระหว่างสององค์ประกอบ a และ b คือความแตกต่างของอันดับ หากองค์ประกอบ a และ b เป็นองค์ประกอบที่ใหญ่ที่สุดลำดับที่ i และ j ในโครงสร้าง ดังนั้นความแตกต่างของอันดับคือ |i - j| หากการค้นหาปกติในโครงสร้างบางอย่างโดยปกติจะใช้เวลา O(f(m)) ดังนั้นการค้นหาองค์ประกอบ a ด้วยองค์ประกอบนิ้ว b ด้วยนิ้วจะต้องใช้เวลา O(f(d)) สังเกตว่าตั้งแต่ d ≤ m จะตามมาว่าในกรณีที่เลวร้ายที่สุด การค้นหาด้วยนิ้วก็แย่พอๆ กับการค้นหาปกติเท่านั้น อย่างไรก็ตาม ในทางปฏิบัติ การค้นหาด้วยนิ้วที่เสื่อมสภาพเหล่านี้ได้ผลมากกว่าการค้นหาปกติ ตัวอย่างเช่น ถ้า f(n) เป็น log(n) และการค้นหาด้วยนิ้วทำการเปรียบเทียบเป็นสองเท่าของการค้นหาปกติในกรณีที่เลวร้ายที่สุด การค้นหาด้วยนิ้วจะช้าลงเมื่อ d> √n ดังนั้น การค้นหาด้วยนิ้วจึงควรใช้ก็ต่อเมื่อสามารถคาดหวังได้อย่างสมเหตุสมผลว่าเป้าหมายจะอยู่ใกล้นิ้วเท่านั้น

การใช้งาน

โครงสร้างข้อมูลยอดนิยมบางโครงสร้างรองรับการค้นหาด้วยนิ้วโดยไม่มีการเปลี่ยนแปลงเพิ่มเติมในโครงสร้างจริง ในโครงสร้างที่ค้นหาองค์ประกอบ a ดำเนินการโดยจำกัดช่วงเวลาที่สามารถค้นหา a ได้ โดยทั่วไปการค้นหาด้วยนิ้วจากองค์ประกอบ b จะดำเนินการโดยการย้อนกลับกระบวนการค้นหาจาก b จนกว่าช่วงเวลาการค้นหาจะมีขนาดใหญ่พอที่จะประกอบด้วยองค์ประกอบ a ที่ การค้นหาจุดใดดำเนินการได้ตามปกติ

เรียงลำดับรายการที่เชื่อมโยง

ในรายการที่เชื่อมโยง ปกติรายการหนึ่งจะค้นหาองค์ประกอบในลักษณะเชิงเส้นโดยการสำรวจจากปลายด้านหนึ่งไปยังอีกด้านหนึ่ง หากรายชื่อที่เชื่อมโยงถูกจัดเรียง และเรามีการอ้างอิงถึงบางโหนดที่มีองค์ประกอบ b แล้ว เราอาจพบองค์ประกอบ a ในเวลา O(d) โดยเริ่มการค้นหาจากองค์ประกอบ b

เรียงลำดับอาร์เรย์

ในอาร์เรย์ที่เรียงลำดับ B โดยปกติเราจะค้นหาองค์ประกอบ a ใน B ด้วยการค้นหาแบบไบนารี การค้นหาด้วยนิ้วดำเนินการโดยใช้การค้นหาด้านเดียวจาก B[j] =b แม้ว่าการค้นหาแบบไบนารีจะลดช่องว่างการค้นหาลงครึ่งหนึ่งหลังจากการเปรียบเทียบแต่ละครั้ง การค้นหาด้านเดียวจะเพิ่มพื้นที่การค้นหาเป็นสองเท่าหลังจากการเปรียบเทียบแต่ละครั้ง โดยเฉพาะอย่างยิ่ง ในการวนซ้ำครั้งที่ k ของการค้นหาด้านเดียว (สมมติว่า a>b) ช่วงที่พิจารณาคือ B[j, j+2 ^k-1 ]. การขยายจะหยุดทันทีที่ B[j + 2 ^k-1 ] ≥ a ณ จุดนี้ช่วงเวลานี้มีการค้นหาแบบไบนารีสำหรับองค์ประกอบ a หากการค้นหาด้านเดียวใช้ k การวนซ้ำเพื่อค้นหาช่วงเวลาที่ประกอบด้วยองค์ประกอบ a มันจะตามมาว่า d> 2 ^k-2 . การค้นหาไบนารีช่วงนี้จะใช้การวนซ้ำอีก k ครั้ง ดังนั้น การค้นหาด้วยนิ้วสำหรับ a จาก b จะใช้เวลา O(k) =O(log d)

.

ข้ามรายการ

ในรายการข้าม เราสามารถใช้นิ้วค้นหาองค์ประกอบ a จากโหนดที่มีองค์ประกอบ b โดยเพียงแค่ทำการค้นหาต่อจากจุดนี้ โปรดทราบว่าหาก a b การค้นหาจะดำเนินการในทิศทางไปข้างหน้า ตัวพิมพ์ย้อนกลับมีความสมมาตรกับการค้นหาปกติในรายการข้าม แต่กรณีไปข้างหน้านั้นซับซ้อนกว่าจริง โดยปกติ การค้นหาในรายการข้ามคาดว่าจะรวดเร็ว เนื่องจากผู้รักษาการณ์ที่จุดเริ่มต้นของรายการถือเป็นโหนดที่สูงที่สุด อย่างไรก็ตาม นิ้วของเราอาจเป็นโหนดของความสูง 1 ด้วยเหตุนี้ เราจึงอาจไม่ค่อยปีนขึ้นไปขณะพยายามค้นหา สิ่งที่ไม่เคยเกิดขึ้นตามปกติ อย่างไรก็ตาม แม้จะมีความยุ่งยากนี้ เราก็สามารถบรรลุ O(log d) เวลาค้นหาที่คาดไว้ได้