daily pastebin goal
2%
SHARE
TWEET

Untitled

pamalau Feb 19th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #binary search
  2. from random import randint
  3.  
  4. def is_Int(s):
  5.     try:
  6.         ii = int(s)
  7.         result = True
  8.     except:
  9.         result = False
  10.     return result
  11.  
  12. def is_Float(s):
  13.     try:
  14.         ff = float(s)
  15.         result = True
  16.     except:
  17.         result = False
  18.     return result
  19.    
  20. def binary_search(sorted_list, item_to_find):
  21.     left = 0
  22.     list_len = len(sorted_list) - 1
  23.     right = list_len
  24.     result = False
  25.     iter = 0;
  26.     pos_list = []
  27.     near_pos = -1
  28.     min_diff = 1e20
  29.    
  30.     while left <= right:
  31.         iter +=1
  32.         mid = int((left + right)/2)
  33.         diff = abs(sorted_list[mid]-item_to_find)
  34.         if diff < min_diff:
  35.             min_diff = diff
  36.             near_pos = mid
  37.         if sorted_list[mid] > item_to_find:
  38.             right = mid - 1
  39.         elif sorted_list[mid] < item_to_find:
  40.             left = mid + 1
  41.         else:
  42.             result = True
  43.             break
  44.     if result: #Check for multiples
  45.         pos_list.append(mid)
  46.         left = mid-1
  47.         while (sorted_list[left] == item_to_find) and (left >= 0):
  48.             pos_list.append(left)
  49.             left -= 1
  50.         right = mid + 1    
  51.         if right <= list_len:    
  52.             while (right <= list_len) and (sorted_list[right] == item_to_find):
  53.                 pos_list.append(right)
  54.                 right += 1
  55.         pos_list = sorted(pos_list)
  56.     return result, sorted_list[mid], pos_list, iter, near_pos
  57. #---------------------------------------    
  58. listx = [1,1,1,2,3,4,5,6,7,18,9,13,10,11,3,12,18,13,3]
  59. listx = sorted(listx)
  60. exit = False
  61. while not exit:
  62.     print(listx)
  63.     inp = input(" Number to find or x to exit : ")
  64.     if inp.lower() != "x":
  65. x
  66. isInt = is_Int(inp)
  67.         isFloat = is_Float(inp)
  68.         if isInt or isFloat:
  69.             if isInt:
  70.                 num_to_find = int(inp)
  71.             else:
  72.                 num_to_find = float(inp)
  73.             found, my_item, pos, iterations, closest_pos = binary_search(listx,num_to_find)
  74.             print('-' * 40)
  75.             if found:
  76.                 print(str(num_to_find) + " found at position "+str(pos) + " in " + str(iterations) + " iterations.")
  77.             else :
  78.                 print(str(num_to_find) + " not found in " + str(iterations) + " iterations.", end="")
  79.                 print(" Closest value to " +str(num_to_find) + " is " + str(listx[closest_pos]))
  80.             print('-' * 40)
  81.     else:
  82.         exit = True
  83. print("User Exited")
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top