Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #binary search
- from random import randint
- def is_Int(s):
- try:
- ii = int(s)
- result = True
- except:
- result = False
- return result
- def is_Float(s):
- try:
- ff = float(s)
- result = True
- except:
- result = False
- return result
- def binary_search(sorted_list, item_to_find):
- left = 0
- list_len = len(sorted_list) - 1
- right = list_len
- result = False
- iter = 0;
- pos_list = []
- near_pos = -1
- min_diff = 1e20
- while left <= right:
- iter +=1
- mid = int((left + right)/2)
- diff = abs(sorted_list[mid]-item_to_find)
- if diff < min_diff:
- min_diff = diff
- near_pos = mid
- if sorted_list[mid] > item_to_find:
- right = mid - 1
- elif sorted_list[mid] < item_to_find:
- left = mid + 1
- else:
- result = True
- break
- if result: #Check for multiples
- pos_list.append(mid)
- left = mid-1
- while (sorted_list[left] == item_to_find) and (left >= 0):
- pos_list.append(left)
- left -= 1
- right = mid + 1
- if right <= list_len:
- while (right <= list_len) and (sorted_list[right] == item_to_find):
- pos_list.append(right)
- right += 1
- pos_list = sorted(pos_list)
- return result, sorted_list[mid], pos_list, iter, near_pos
- #---------------------------------------
- listx = [1,1,1,2,3,4,5,6,7,18,9,13,10,11,3,12,18,13,3]
- listx = sorted(listx)
- exit = False
- while not exit:
- print(listx)
- inp = input(" Number to find or x to exit : ")
- if inp.lower() != "x":
- x
- isInt = is_Int(inp)
- isFloat = is_Float(inp)
- if isInt or isFloat:
- if isInt:
- num_to_find = int(inp)
- else:
- num_to_find = float(inp)
- found, my_item, pos, iterations, closest_pos = binary_search(listx,num_to_find)
- print('-' * 40)
- if found:
- print(str(num_to_find) + " found at position "+str(pos) + " in " + str(iterations) + " iterations.")
- else :
- print(str(num_to_find) + " not found in " + str(iterations) + " iterations.", end="")
- print(" Closest value to " +str(num_to_find) + " is " + str(listx[closest_pos]))
- print('-' * 40)
- else:
- exit = True
- print("User Exited")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement