• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

pamalau Feb 19th, 2019 77 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.

Top