Advertisement
cartagenae

Binary Search (recursive) 2

Nov 18th, 2018
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.92 KB | None | 0 0
  1. def binary_search(sorted_list, left_pointer, right_pointer, target):
  2. # this condition indicates we've reached an empty "sub-list"
  3. if left_pointer >= right_pointer:
  4. return "value not found"
  5.  
  6. # We calculate the middle index from the pointers now
  7. mid_idx = (left_pointer + right_pointer) // 2
  8. mid_val = sorted_list[mid_idx]
  9.  
  10. if mid_val == target:
  11. return mid_idx
  12. if mid_val > target:
  13. # we reduce the sub-list by passing in a new right_pointer
  14. return binary_search(sorted_list, left_pointer, mid_idx, target)
  15. if mid_val < target:
  16. # we reduce the sub-list by passing in a new left_pointer
  17. return binary_search(sorted_list, mid_idx + 1, right_pointer, target)
  18.  
  19. values = [77, 80, 102, 123, 288, 300, 540]
  20. start_of_values = 0
  21. end_of_values = len(values)
  22. result = binary_search(values, start_of_values, end_of_values, 288)
  23.  
  24. print("element {0} is located at index {1}".format(288, result))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement