1_2_binary_search_with_time.py

# -*- coding: utf-8 -*-
"""1.2.Binary Search With Time.ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/1OrKP5NApLuYquivMf2YDMyA5swMg6-Uz
"""

import time
import random
import matplotlib.pyplot as plt

def binary_search(arr, low, high, key):
    if high >= low:
        mid = (low + high) // 2
        if arr[mid] == key:
            return mid
        elif arr[mid] > key:
            return binary_search(arr, low, mid-1, key)
        else:
            return binary_search(arr, mid+1, high, key)
    return -1

sizes = [100, 500, 1000, 5000, 10000]
times = []

for size in sizes:
    arr = sorted(random.sample(range(size*10), size))
    key = arr[-1]
    start = time.time()
    binary_search(arr, 0, len(arr)-1, key)
    end = time.time()
    times.append(end - start)

plt.plot(sizes, times, marker='x')
plt.xlabel("Number of Elements (n)")
plt.ylabel("Time (s)")
plt.title("Binary Search Time vs n")
plt.grid(True)
plt.show()