เมื่อจำเป็นต้องดำเนินการค้นหาแบบไบนารีโดยไม่ใช้พจนานุกรม สามารถกำหนดวิธีการที่จะตรวจสอบดัชนีแรกและดัชนีสุดท้ายของรายการ และรับค่าตรงกลางของรายการ
แล้วนำไปเปรียบเทียบกับค่าที่ต้องตรวจสอบ หากพบ ค่าจะถูกส่งคืน มิฉะนั้น -1 จะถูกส่งคืน
สิ่งสำคัญคือต้องจำไว้ว่าการค้นหาแบบไบนารีใช้งานได้กับองค์ประกอบที่เรียงลำดับเท่านั้น ไม่ว่าจะเรียงลำดับจากน้อยไปมากหรือมากไปหาน้อย
สามารถใช้รายการเพื่อเก็บค่าที่แตกต่างกัน (เช่น ข้อมูลของประเภทข้อมูลใดๆ เช่น จำนวนเต็ม จุดลอยตัว สตริง และอื่นๆ)
ด้านล่างนี้เป็นการสาธิตสำหรับสิ่งเดียวกัน -
ตัวอย่าง
def binary_search(my_list, elem):
low = 0
high = len(my_list) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if my_list[mid] < elem:
low = mid + 1
elif my_list[mid] > elem:
high = mid - 1
else:
return mid
return -1
my_list = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
elem_to_search = 1
print("The list is")
print(my_list)
my_result = binary_search(my_list, elem_to_search)
if my_result != -1:
print("Element found at index ", str(my_result))
else:
print("Element not found!") ผลลัพธ์
The list is [1, 9, 11, 21, 34, 54, 67, 90] Element found at index 0
คำอธิบาย
- มีการกำหนดเมธอดที่ชื่อ 'binary_search' ซึ่งรับรายการและองค์ประกอบที่จะค้นหาเป็นพารามิเตอร์
- ตัวแปรระดับต่ำถูกกำหนดเป็น 0 และตัวแปรระดับกลางถูกกำหนดเป็น 0
- ตัวแปรสูงถูกกำหนดความยาวของรายการ-1
- ทำการหารระดับบิตเพื่อรับค่าสำหรับตัวแปร 'กลาง' เฉพาะในกรณีที่ค่า 'ต่ำ' น้อยกว่าหรือเท่ากับ 'สูง'
- ขั้นแรกให้ค้นหาองค์ประกอบจากดัชนีระดับต่ำถึงระดับกลาง หากค่าน้อยกว่าค่าที่ปรากฏที่ดัชนีระดับกลาง
- มิฉะนั้น องค์ประกอบจะถูกค้นหาจากดัชนีกลางถึงสูง หากค่ามากกว่ากลางและน้อยกว่าสูง
- ตอนนี้ รายการถูกกำหนดแล้ว
- เมธอดนี้เรียกโดยส่งรายการด้านบนเป็นพารามิเตอร์
- ข้อมูลการดำเนินการนี้ถูกเก็บไว้ในตัวแปร
- ตัวแปรนี้คือเอาต์พุตที่แสดงบนคอนโซล
