Binary Search Algorithm - Project Ideas
I'm writing a python project about binary search, but I would like to be able to implement a graphical interface for this algorithm. Do you have any ideas how I could use this algorithm so that I can implement the interface? I mean project ideas , not the implementation itself ..
Thank you
This is my code :
# It returns index of x in given array arr if present,
# else returns -1
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# If x is greater, ignore left half
if arr[mid] < x:
low = mid + 1
# If x is smaller, ignore right half
elif arr[mid] > x:
high = mid - 1
# means x is present at mid
else:
return mid
# If we reach here, then the element was not present
return -1
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Function call
result = binary_search(arr, x)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")```
Although you asked for graphical interface, still just for fun I decided to implement following simple ASCII-art visualization for your task of Binary Search, it might be useful for you to give you some ideas.
I used some ANSI escape codes when drawing graphics into console. This escape codes on Windows needs installing one time colorama module python -m pip install colorama. On Linux it doesn't need installing anything.
Code can be tweeked to different random seed value or amount of numbers or size of numbers (up to 100, up to 1000, etc). Values are chosen randomly with fixed seed value (change value in random.seed(...) line).
First I show ASCII-video screencast recorded on my Linux (asciinema link), then code:
Code:
import platform, time, sys
if platform.system() == 'Windows':
import colorama
colorama.init()
def vis(data, steps):
def str_set(s, i, c):
return s[:i] + c + s[i + 1:]
def astr_set(a, j, i, c):
a[j] = str_set(a[j], i, c)
dlen = max(len(str(e)) for e in data) + 1
loline = ''.join(str(e).zfill(dlen - 1) + '|' for e in data)
ll = len(loline)
N = len(steps)
h1 = 3
lines = [' ' * ll for e in range(h1 * N)] + [loline]
def emit_frame():
sys.stdout.write("\033[F" * len(lines) + '\n'.join(lines) + '\n')
time.sleep(1)
emit_frame()
for i in range(N - 1):
lpcur, lpnext = [dlen * steps[i + e] + (dlen - 2) // 2 for e in (0, 1)]
for j in range(h1 - 1):
astr_set(lines, i * h1 + j, lpcur, '|')
dir_ = -1 if steps[i + 1] < steps[i] else +1 if steps[i + 1] > steps[i] else 0
for j in range((i + 1) * h1, len(lines) - 1):
astr_set(lines, j, lpcur, '.' if j < len(lines) - 2 else '?')
for j in range(lpcur, lpnext + dir_, dir_):
astr_set(lines, (i + 1) * h1 - 1, j, ('/' if dir_ < 0 else '\\') if j in (lpcur, lpnext) else '-')
if j == lpcur:
emit_frame()
if i == N - 2:
for j in range((i + 1) * h1, len(lines) - 1):
astr_set(lines, j, lpnext, '|' if j < len(lines) - 2 else 'V')
emit_frame()
def binary_search(f, l, r, target):
steps = []
while l <= r:
m = (l + r) // 2
steps.append(m)
fm = f(m)
if fm < target:
l = m + 1
elif fm > target:
r = m - 1
else:
break
return steps
def main():
import random
random.seed(3)
data = sorted(random.randrange(100) for i in range(30))
target = data[random.randrange(len(data))]
steps = binary_search(lambda x: data[x], 0, len(data) - 1, target)
vis(data, steps)
if __name__ == '__main__':
main()
Final output:
|
|
\-----------------------\
. |
. |
. \-----------\
. . |
. . |
. . /-----/
. . | .
. . | .
. . /--/ .
. . | . .
. . | . .
? ? V ? ?
01|08|16|19|19|24|29|29|30|33|47|49|50|60|60|60|60|66|69|69|70|70|74|75|77|77|80|81|81|91|
Also I created slightly modified infinite ASCII-screencast version of my code (download code here or or Try it online) which produces next fast-playing video (asciinema link):
And one more version which uses Unicode chars to draw nice arrows and lines, also it shows much denser tree, uses more numbers to search from (download code here, or Try it online), you get next video (asciinema link), open next video image in the new tab/window of browser to see it even more nicer and bigger:
And another one trial to make even more advanced code and visualization. Now it is two level visualization, first half of steps is drawn vertically and remaining steps are drawn horizontally. This is done to achieve higher density of image, to put mor numbers on the console screen.
As usual, download code here and/or Try it online here. Resulting video is below (plus asciinema link):
