Python Tutor Online: Binary Search algorithm Python

What is Linear Search?

Dear Readers,

In this Algorithm the way of searching an element from an array is to sort it and them keep dividing it on the basis of its value of elements v/s the desired element to be checked.

It wouldn't be wrong to say a picture is worth thousand words so:

# Note here middle for arr = [1,2,3,4] would be 3 since len(list) ==4//2 ==>2 and arr[2] = 3

↕ ↕ ↕ ↕

indice's for arr-==> 0 1 2 3

So there are basic steps involved:

Step 1: sorting the entered elements in array

Step 2:then get the key(desired element to be checked) from input

Step 3 :Set low value equal to zero and high value = len(list)-1

Step 4: calculate the middle value of array using average of low value and high value ((low+high)//2)

Step 5:then take middle element of array and match with key(38)

Step 6: If it matches quit with index of element

Step 7:Else if the key value is greater than mid value set low value as next to mid value and keep high value as same(i.e 45 will be new low and high will be 90 )

Step 6:and if the key value is less than mid value set high value just behind mid value and keep low value as same(i.e 6 will be new low and high will be 23 )

Step 8: again calculate the middle values respectively (i.e if Step 5 new_mid will be 77 and for Step 6

new_mid would be 12)

Step 9: This process will repeat until key matchs with middle value.

# its time complexity is O(logn)

===>Here's the code in python so it makes it easy to interpret for beginners:

# Returns index of x in arr if present, else -1 
def binary_search(arr, low, high, x): 

	# Check base case 
	if high >= low: 

		mid = (high + low) // 2

		# If element is present at the middle itself 
		if arr[mid] == x: 
			return mid 

		# If element is smaller than mid, then it can only 
		# be present in left subarray 
		elif arr[mid] > x: 
			return binary_search(arr, low, mid - 1, x) 

		# Else the element can only be present in right subarray 
		else: 
			return binary_search(arr, mid + 1, high, x) 

	else: 
		# Element is not present in the array 
		return -1

# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10

# Function call 
result = binary_search(arr, 0, len(arr)-1, x) 

if result != -1: 
	print("Element is present at index", str(result)) 
else: 
	print("Element is not present in array")

I hope you liked this blog on Binary Search you can check out more such blogs on my blogspot and for more info on this topic : click here!

Python Tutor Online

Friday, November 6, 2020

Binary Search algorithm Python

What is Linear Search?

Linear Search algorithm