ในบทความนี้ เราจะเรียนรู้เกี่ยวกับวิธีแก้ปัญหาและแนวทางแก้ไขปัญหาที่กำหนด
คำชี้แจงปัญหา - เราจะได้รับรายการที่จัดเรียงและเราจำเป็นต้องค้นหาองค์ประกอบโดยใช้การค้นหาแบบไบนารี
อัลกอริทึม
-
เปรียบเทียบ x กับองค์ประกอบตรงกลาง
-
หาก x ตรงกับองค์ประกอบตรงกลาง เราจะคืนค่าดัชนีกลาง
-
มิฉะนั้น ถ้า x มากกว่าองค์ประกอบกลาง แล้ว x สามารถอยู่ในอาร์เรย์ย่อยครึ่งทางขวาหลังองค์ประกอบกลางเท่านั้น ดังนั้นเราจึงเกิดซ้ำสำหรับครึ่งขวา
-
อย่างอื่น (x น้อยกว่า) เกิดขึ้นอีกสำหรับครึ่งซ้าย
อัลกอริทึมแบบเรียกซ้ำ
ตัวอย่าง
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index "+str(result))
else:
print ("Element is not present in array") อัลกอริธึมวนซ้ำ
ตัวอย่าง
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index "+str(result))
else:
print ("Element is not present in array") Element is present at index 4
บทสรุป
ในบทความนี้ เราได้เรียนรู้เกี่ยวกับวิธีการใช้ Binary Search
