karlakmkj

Binary search sample using loop

Jan 7th, 2021 (edited)
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.04 KB | None | 0 0
  1. def binary_search(searchList, searchTerm):
  2.     #First, the list must be sorted.
  3.     searchList.sort()
  4.  
  5.     #Now, each iteration of the loop, we want to narrow down the part of the list to look at. So, we need to keep track of the range we've narrowed down to so far. Initially, that will be the entire list, from the first index to the last.
  6.     min = 0
  7.     max = len(searchList) - 1
  8.    
  9.     #Now, we want to loop as long as our range has any numbers left to investigate. As long as there is more than one number between minimum and maximum, we're not done searching.
  10.     while min <= max:
  11.         print("Searching for", searchTerm, "in", searchList[min:max+1])
  12.  
  13. '''        
  14. We want to check the middle item of the current range, which is the average of the current minimum and maximum index. For example, if min was 5 and max was 15, our middle number would be at index 5. We'll use floor division because indices must be integers.
  15. '''
  16.         currentMiddle = (min + max) // 2
  17.         #If the term in the middle is the term we're looking for, we're done!
  18.         if searchList[currentMiddle] == searchTerm:
  19.             print(searchTerm, "==", searchList[currentMiddle], "-- search term found!")
  20.             return True
  21.  
  22.         #If not, we want to check if the term we're looking for should come earlier or later.
  23.  
  24.         #If the term we're looking for is less than the current middle, then search the first half of the list:
  25.         elif searchTerm < searchList[currentMiddle]:
  26.             print(searchTerm, "<", searchList[currentMiddle], "-- repeating for left side.")
  27.             max = currentMiddle - 1
  28.  
  29.         #If the term we're looking for is greater than the current middle, search the second half of the list:
  30.         else:
  31.             print(searchTerm, ">", searchList[currentMiddle], "-- repeating for right side.")
  32.             min = currentMiddle + 1
  33.  
  34. '''          
  35. Each iteration of the loop, one of three things happens: the term is found, max shrinks, or min grows. Eventually, either the term will be found, or min will be equal to max.
  36.  
  37. If the search term was found, this line will never be reached because the return statement will end the function. So, if we get this
  38. far, then the search term was not found, and we can return False.
  39. '''
  40.     print(searchTerm, "never found.")
  41.     return False
  42.  
  43. intlist = [12, 64, 23, 3, 57, 19, 1, 17, 51, 62]
  44. print("23 is in intlist:", binary_search(intlist, 23))
  45. print("50 is in intlist:", binary_search(intlist, 50))
  46.  
  47. #Because of the way Python handles types, this exact same function works for any sortable data type. Check it out with strings:
  48. strlist = ["David", "Joshua", "Marguerite", "Jackie"]
  49. print("David is in strlist:", binary_search(strlist, "David"))
  50. print("Lucy is in strlist:", binary_search(strlist, "Lucy"))
  51.  
  52. #Or with dates!
  53. from datetime import date
  54. datelist = [date(1885, 10, 13), date(2014, 11, 29), date(2016, 11, 26)]
  55. print("10/13/1885 is in datelist:", binary_search(datelist, date(1885, 10, 13)))
  56. print("11/28/2015 is in datelist:", binary_search(datelist, date(2015, 11, 28)))
Add Comment
Please, Sign In to add comment