[go: up one dir, main page]
Scribd
Upload
34 views2 pages

Binary Search & Time Complexity

The document contains a Python implementation of a recursive binary search function, which searches for a target value in a sorted array. It includes an example usage that measures the time taken to find a specific target and plots the time complexity of the binary search algorithm against varying input sizes. The plot visualizes how the execution time changes as the input size increases.

Uploaded by

iraniyan.teachnotes
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
34 views2 pages

Binary Search & Time Complexity

The document contains a Python implementation of a recursive binary search function, which searches for a target value in a sorted array. It includes an example usage that measures the time taken to find a specific target and plots the time complexity of the binary search algorithm against varying input sizes. The plot visualizes how the execution time changes as the input size increases.

Uploaded by

iraniyan.teachnotes
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

import matplotlib.

pyplot as plt

import time

def binary_search_recursive(arr, target, low, high):

if low > high:

return -1

mid = (low + high) // 2

if arr[mid] == target:

return mid

elif arr[mid] > target:

return binary_search_recursive(arr, target, low, mid-1)

else:

return binary_search_recursive(arr, target, mid+1, high)

# Example usage

arr = [1, 3, 5, 7, 9, 100 ,770]

target = 770

start_time = time.time()

index = binary_search_recursive(arr, target, 0, len(arr)-1)

end_time = time.time()

print("Index of", target, "in", arr, "is", index)

print("Time taken:", end_time - start_time)

# Plotting time complexity

arr_size = 100000
arr = [i for i in range(arr_size)]

target = arr[-1]

times = []

for i in range(arr_size):

start_time = time.time()

binary_search_recursive(arr, target, 0, len(arr)-1)

end_time = time.time()

times.append(end_time - start_time)

plt.title("Binary Search Time Complexity")

plt.xlabel("Input size")

plt.ylabel("Time takem")

plt.plot(times)

plt.show()

You might also like