Advertisement
davidhellam

Python: Binary Search Stuff

Aug 20th, 2019
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.63 KB | None | 0 0
  1. import random
  2.  
  3. values = []
  4. def generate(samplesize,samplerange):
  5.     for count in range(samplesize):
  6.         nextnumber = random.randint(1,samplerange)
  7.         values.append(nextnumber)
  8.     #print(values)
  9.     values.sort()
  10.     #print(values)
  11.        
  12. def binsearch(values,number):
  13.     found = False
  14.     lower = 0
  15.     upper = len(values)-1
  16.     mid = int((upper+lower)/2)
  17.     while not found and lower<=upper:
  18.         mid = int((upper+lower)/2)
  19.         #print(str(lower)+" - "+str(mid)+" - "+str(upper))
  20.         if values[mid]>number:
  21.             upper = mid -1
  22.         elif values[mid]<number:
  23.             lower = mid + 1
  24.         else:
  25.             found=True
  26.     if found:
  27.         return mid
  28.     else:
  29.         return -1
  30.  
  31. def locaterange(values, number):
  32.     target = binsearch(values,number)
  33.     if target >-1:
  34.         lower = target
  35.         upper = target
  36.         found = False
  37.         while not found:
  38.             if lower>0:
  39.                 if values[lower-1]==values[lower]:
  40.                     lower=lower-1
  41.                 else:
  42.                     found=True
  43.             else:
  44.                 found=True
  45.         found = False
  46.         while not found:
  47.             if upper<len(values)-1:
  48.                 if values[upper+1]==values[upper]:
  49.                     upper=upper+1
  50.                 else:
  51.                     found = True
  52.             else:
  53.                 found = True
  54.         return[lower,upper]
  55.     else:
  56.         return "Not Found!"
  57.    
  58. generate(100,100)
  59. mynumber = 100
  60. print(binsearch(values,mynumber))
  61. print(locaterange(values,mynumber))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement