m2skills

bsearch python

Mar 30th, 2017
283
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.87 KB | None | 0 0
  1. # method for binary search
  2. def binarySearch(element, myList2):
  3.    
  4.     # initially values for upper and lower bounds
  5.     low = 0
  6.     high = len(myList) - 1
  7.    
  8.     # boolean variable to indicate that the element has been found
  9.     found = False
  10.    
  11.     # loop till high is greater than low or till the element is not found
  12.     while low <= high and found is False:
  13.    
  14.         # calculate the mid value
  15.         mid = int((low + high)/2)
  16.        
  17.         # compare the mid value with the element
  18.         # if equal then print the position and return
  19.         if myList2[mid] == element:
  20.             print("Element " + str(element) + " found at position " + str(mid + 1))
  21.             found = True
  22.             break
  23.            
  24.         # else if the middle value if greater than the element
  25.         # then element lies on the left side of the mid so decrease high value
  26.         elif myList2[mid] > element:
  27.             high = mid - 1
  28.            
  29.         # else if the middle value if less than the element
  30.         # then element lies on the right side of the mid so increase low value 
  31.         elif myList2[mid] < element:
  32.             low = mid + 1
  33.    
  34.     # display this if element not found
  35.     if found is False:
  36.         print("Element " + str(element) + " not present in the List")
  37.        
  38.     return
  39.    
  40. # main function
  41.  
  42. # accepts comma seperated values for the list
  43. myList = list(map(int, input("Enter the Elements of the List : ").strip().split(',')))
  44.  
  45.  
  46. # binary search requires the list to be sorted to begin searching
  47. myList.sort()
  48. print("The sorted List is : ")
  49. print(myList)
  50.  
  51. binarySearch(8, myList)
  52. binarySearch(232, myList)
  53. binarySearch(4235, myList)
  54. binarySearch(7, myList)
  55. binarySearch(1, myList)
  56.  
  57. '''
  58. Enter the Elements of the List : 12,23,5475,679,790,9232,232,4235,13,1,6
  59. The sorted List is :
  60. [1, 6, 12, 13, 23, 232, 679, 790, 4235, 5475, 9232]
  61. Element 8 not present in the List
  62. Element 232 found at position 6
  63. Element 4235 found at position 9
  64. Element 7 not present in the List
  65. Element 1 found at position 1
  66.  
  67.  
  68. '''
Add Comment
Please, Sign In to add comment