Python - การค้นหาอัลกอริทึม

การค้นหาเป็นสิ่งจำเป็นขั้นพื้นฐานเมื่อคุณจัดเก็บข้อมูลในโครงสร้างข้อมูลที่แตกต่างกัน การประเมินที่ง่ายที่สุดคือการดูทุกองค์ประกอบในโครงสร้างข้อมูลและจับคู่กับค่าที่คุณกำลังค้นหา สิ่งนี้เรียกว่าการค้นหาเชิงเส้น มันไม่มีประสิทธิภาพและไม่ค่อยได้ใช้งาน แต่การสร้างโปรแกรมขึ้นมานั้นให้แนวคิดว่าเราจะใช้อัลกอริทึมการค้นหาขั้นสูงได้อย่างไร

การค้นหาเชิงเส้น

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

def linear_search(values, search_for):
    search_at = 0
    search_res = False

# Match the value with each data element	
    while search_at < len(values) and search_res is False:
        if values[search_at] == search_for:
            search_res = True
        else:
            search_at = search_at + 1

    return search_res

l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))

เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -

True
False

Interpolation Search

อัลกอริทึมการค้นหานี้ทำงานกับตำแหน่งการตรวจสอบของค่าที่ต้องการ เพื่อให้อัลกอริทึมนี้ทำงานได้อย่างถูกต้องการรวบรวมข้อมูลควรอยู่ในรูปแบบที่เรียงลำดับและกระจายอย่างเท่าเทียมกัน ในขั้นต้นตำแหน่งโพรบคือตำแหน่งของรายการที่อยู่ตรงกลางส่วนใหญ่ของคอลเลกชันหากการจับคู่เกิดขึ้นดัชนีของรายการจะถูกส่งกลับ ถ้ารายการกลางมากกว่ารายการตำแหน่งโพรบจะถูกคำนวณอีกครั้งในอาร์เรย์ย่อยทางด้านขวาของรายการกลาง มิฉะนั้นรายการจะถูกค้นหาใน subarray ทางด้านซ้ายของรายการตรงกลาง กระบวนการนี้ยังคงดำเนินต่อไปในอาร์เรย์ย่อยเช่นกันจนกว่าขนาดของ subarray จะลดลงเป็นศูนย์

มีสูตรเฉพาะในการคำนวณตำแหน่งกลางซึ่งระบุไว้ในโปรแกรมด้านล่าง

def intpolsearch(values,x ):
    idx0 = 0
    idxn = (len(values) - 1)

    while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:

# Find the mid point
	mid = idx0 +\
               int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
                    * ( x - values[idx0])))

# Compare the value at mid point with search value 
        if values[mid] == x:
            return "Found "+str(x)+" at index "+str(mid)

        if values[mid] < x:
            idx0 = mid + 1
    return "Searched element not in the list"


l = [2, 6, 11, 19, 27, 31, 45, 121]
print(intpolsearch(l, 2))

เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -

Found 2 at index 0