Advertisement
pamalau

Untitled

Feb 19th, 2019
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.46 KB | None | 0 0
  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")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement