repl.it
@charles2588/

Binary Search

Python

No description

fork
loading
Files
  • main.py
main.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
#Binary Search
def binarysearch(arr,searchterm):
	start=0 #we need start and end to calculate pivot
	end=len(arr)-1
	while(start<=end):#when to stop when start and end cross each other
		pivot=int((start+end)/2)
		if(arr[pivot])==searchterm:
			return True
		elif(arr[pivot]>searchterm):
			end=pivot-1		#search left when pivot item is bigger
		else:
			start=pivot+1
	return False
	
#Recursive Implementation of Bindary search
def recursivebinarysearch(arr,searchterm):
	pivot=int(len(arr)/2)
	if(pivot==0):
		if(arr[pivot]!=searchterm):
			return False	
	if(arr[pivot]==searchterm):
		return True
	elif(arr[pivot]>searchterm):
		return recursivebinarysearch(arr[:pivot],searchterm)
	else:
		return recursivebinarysearch(arr[pivot+1:],searchterm)
	

print(binarysearch(sorted([1,5,8,2,4,-5,6,7]),8))
print(binarysearch(sorted([1,5,8,2,4,-5,6,7]),-5))
print(binarysearch(sorted([1,5,8,2,4,-5,6,7]),0))

print(recursivebinarysearch(sorted([1,5,8,2,4,-5,6,7]),8))
print(recursivebinarysearch(sorted([1,5,8,2,4,-5,6,7]),-5))
print(recursivebinarysearch(sorted([1,5,8,2,4,-5,6,7]),0))