I'm relatively new to python, so I'm not big on the efficieny aspect of it, which is why, when I wrote two algorithms to search for an element, I was surprised
'''
Making an array with data that can be stored easily
Setting up pointers in data using lists
'''
import time
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] #starting / defining the array i need for the binary seach to work
process_arr = []
ctr = 0
def ARR_SEARCH(INPUT):
start = time.time()
# Have to set R and L in order to find the middle element of this
l = 0
r = len(arr)-1
mid = None
returntup = None
while r > l:
mid = (l+ (r-l))//2 # The R - L is to ensure that it is the mid
if(arr[mid] == INPUT):
end = time.time() - start
r = 0
returntup = mid, end
elif(arr[mid] > INPUT):
r = mid-1
elif(arr[mid] < INPUT):
l = mid+1
if returntup!=None:
return returntup
else:
return -1, 0
def binarySearch (arr, l, r, x):
start = time.time()
# Check base case
if r >= l:
mid = l + (r - l)//2
# If element is present at the middle itself
if arr[mid] == x:
end = time.time() - start
print("BINARY END ", end)
returntup = mid, end
return returntup
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
def BRUTE_FORCE_v2(INPUT):
start = time.time()
ctr = -1
for i in arr:
ctr += 1
if i==INPUT:
end = time.time() - start
print("BRUTE END" , end)
returntup = ctr, end
return returntup
else:
continue
else:
end = time.time() - start
returntup = -1, end
return returntup
def BRUTE_FORCE(INPUT):
start = time.time()
for i in range(len(arr)):
if arr[i]==INPUT:
end = time.time() - start
returntup = i, end
return returntup
else:
continue
else:
end = time.time() - start
returntup = -1, end
return returntup
search = int(input("Enter the required search element"))
out1 = BRUTE_FORCE(search)
out2 = binarySearch(arr, 0, (len(arr)-1), search)
out3 = BRUTE_FORCE_v2(search)
diff1 = out1[1] - out2[1]
diff2 = out1[1] - out3[1]
diff3 = out3[1] - out2[1]
print("Brute vs Force Ratio in this case is: \n \n ", diff1)
print("\n \n \n \n ")
print("The difference between the normal and the upgraded brute force algorithm in this case is: \n \n", diff2)
print("\n \n \n \n ")
print("So, the effective time differnece between the two actual algs are: \n \n ", diff3)
The output of this program is as follows
Enter the required search element8
BINARY END 1.430511474609375e-06
BRUTE END 2.6226043701171875e-06
Brute vs Force Ratio in this case is:
5.7220458984375e-06
The difference between the normal and the upgraded brute force algorithm in this case is:
4.5299530029296875e-06
So, the effective time differnece between the two actual algs are:
1.1920928955078125e-06
This makes perfect sense, even for a small list, binary search trumps out bruteforce
BUT
What's interesting here is when I search for the element '1'
1 is in the beginning of the list, and bruteforce, should ideally, find it first. BUT binary search somehow beats it
My output, when I search for 1, is this
Enter the required search element1
BINARY END 1.430511474609375e-06
BRUTE END 2.86102294921875e-06
Brute vs Force Ratio in this case is:
5.245208740234375e-06
The difference between the normal and the upgraded brute force algorithm in this case is: 3.814697265625e-06
So, the effective time differnece between the two actual algs are:
1.430511474609375e-06
If you were wondering why there are two bruteforce algorithms, one is for the python implementation of iterating through lists, and one is the regular array parsing implementation
Im calculating the difference between the python implementation of list parsing, as it looks to be faster than the other implementation, and finding the difference between the times.
As a fact, simple because the bruteforce has to make only one comparison, it has to be faster than the binary search, but why isn't it?
Could someone answer the question?
PS: This code does not play well with idle, and it outputs 0.0 for all end times. Terminal seems to give the right output though....
As mentioned by @kaya3
This was indeed a clock error. It looks like the first result was by pure chance, and checking this out for a larger number of iterations, or using the libraries mentioned gives the desired values.