-
Notifications
You must be signed in to change notification settings - Fork 1
/
19_linear_search_plus.py
151 lines (130 loc) · 4.56 KB
/
19_linear_search_plus.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
"""
Write a Program to enter the numbers and find Linear Search, Binary Search,
Lowest Number and Selection Sort using array code.
"""
ARRAY = []
def selection_sort(array: list):
__len = len(array)
# Traverse thru list
for i in range(0, __len):
__select = i
# traverse through the unsorted part,
for j in range(i+1, __len):
if array[__select] > array[j]:
__select = j # __select becomes the index of the lowest element
# swap i th with the lowest currently
array[i], array[__select] = array[__select], array[i]
return array
def linear_search(array: list, element: int):
# doesnt need sorted array
for i in range(len(array)):
if array[i] == element:
return i
return -1 # This is not reached if element is present
def binary_search_recursion(array: list, element: int, start_index: int, end_index: int):
# needs sorted array
if end_index >= start_index: # prevents infinite recursion
if len(array[start_index:end_index]) == 0:
return -1
middle = start_index + (end_index - start_index) // 2
if array[middle] == element:
return middle
elif array[middle] > element:
return binary_search_recursion(array, element, start_index, middle - 1)
elif array[middle] < element:
return binary_search_recursion(array, element, middle + 1, end_index)
else:
return -1
else:
return -1
def binary_search_iteration(array: list, element: int):
#needs sorted array
start = 0
end = len(array) - 1
while end >= start:
mid = (end + start) // 2
if array[mid] == element:
return mid
elif array[mid] > element: # element comes before mid
end = mid - 1
elif array[mid] < element: # element comes after mid
start = mid + 1
# if we reach here element was not present
return -1
def lowest_number(array:list):
__min = 0
for element in array:
if __min > element:
__min = element
return __min
def main():
global ARRAY
__choice = 0
while __choice != 99:
print("""
+----------MENU----------+
| 1. Populate Array |
| 2. Print Array |
| 3. Selection Sort |
| 4. Linear Search |
| 5. Binary Search - R |
| 6. Binary Search - I |
| 7. Lowest Term |
| 99. Quit |
+------------------------+
""")
__choice = int(input(">>> "))
if __choice == 1:
__input = input('Comma Seperated Integers: ')
ARRAY += [int(item) for item in __input.split(',')]
elif __choice == 2:
print(ARRAY)
elif __choice == 3:
print(f"BEFORE SORT: {ARRAY}")
print(f"AFTER SORT: {selection_sort(ARRAY)}")
elif __choice == 4:
__array = selection_sort(ARRAY)
print(f"ARRAY = {__array}")
__element = int(input('Enter Search Term: '))
__result = linear_search(__array, __element)
if __result != -1:
print(f"{__element} is at {__result} position")
else:
print("Search yielded no results.")
elif __choice == 5:
__array = selection_sort(ARRAY)
print(f"ARRAY = {__array}")
__element = int(input('Enter Search Term: '))
__result = binary_search_recursion(__array, __element, 0, len(__array))
if __result != -1:
print(f"{__element} is at {__result} position")
else:
print("Search yielded no results.")
elif __choice == 6:
__array = selection_sort(ARRAY)
print(f"ARRAY = {__array}")
__element = int(input('Enter Search Term: '))
__result = binary_search_iteration(__array, __element)
if __result != -1:
print(f"{__element} is at {__result} position")
else:
print("Search yielded no results.")
elif __choice == 7:
print(f"Lowest Term in Array is {lowest_number(ARRAY)}")
if __name__ == "__main__":
main()
__OUTPUT__ = """
+----------MENU----------+
| 1. Populate Array |
| 2. Print Array |
| 3. Selection Sort |
| 4. Linear Search |
| 5. Binary Search - R |
| 6. Binary Search - I |
| 7. Lowest Term |
| 99. Quit |
+------------------------+
>>> 3
BEFORE SORT: [13, 14, 15, 1, 3, 2, 19]
AFTER SORT: [1, 2, 3, 13, 14, 15, 19]
"""