Python Binary Search

Here you’ll study python binary search with program and rule.

In a linear search, we’ve got to examine every node/element. thanks to this, time complexness will increase. to cut back this point complexness, we tend to use Binary search. In Binary search half, the given array is going to be neglected when only one comparison.

The main purpose to be noted is Binary Search solely works for the sorted array.

If the array is sorted into ascending order, all we’ve got to try and do is use the centre index of the array then compare the part at middle index with the element to seek out. If our given part is larger than the element at middle index then we’ll ignore the left 0.5 arrays and therefore the array can begin from the consequent index of middle index.

On the alternative hand, if the given part is a smaller amount than the element presents at middle index, then we’ll ignore the proper 0.5 arrays and therefore the new array can end with left one index of middle index.

If the given part is adequate to the element presents on the centre index, then the search is completed.

In the case, the primary index is larger than the last index of the array, it suggests that we’ve got been capable of the complete array and therefore the given part isn’t conferred within the array.

Python Binary Search

Example:

We have a sorted array [2, 14, 19, 21, 99, 210, 512, 1028, 4443, 5110] and therefore the part to be noticed is 4443.

We primarily ignore half the weather simply when one comparison.

Compare x with the centre part.
If x matches with a middle part, we tend to come back to the middle index.

Else If x is larger than the middle part, then x will solely be right 0.5 subarrays when the middle part. thus we tend to recur for right 0.5.
Else (x is smaller) recur for the left 0.5.

Algorithm:

Binary_search [arr, starting index, last index, element]
Step:1-  mid = (starting index + last index) / 2
Step:2-  If starting index > last index
		Then, Print "Element not found" 
			Exit
 
         Else if element > arr[mid]
		   Then,  starting index = mid + 1
		   Go to Step:1
	
	     Else if element < arr[mid]
		   Then, last index = mid -  1
	     	Go to Step:2
	
	     Else:
		   { means element == arr[mid] }
		   Print "Element Presented at position" + mid
		   Exit

Program for Binary Search in Python

Iterative Approach (Loop):

def Binary_search(arr,start_index,last_index,element):
	while (start_index<= last_index):
		mid =(int)(start_index+last_index)/2
		if (element>arr[mid]):
			start_index = mid+1
		elif (element<arr[mid]):
			last_index = mid-1
		elif (element == arr[mid]):
			return mid
	return -1
	
arr = [2,14,19,21,99,210,512,1028,4443,5110]
element = 4443
start_index = 0
last_index = len(arr)-1
found = Binary_search(arr,start_index,last_index,element)
if (found == -1):
	print "element not present in array"
else:
	print "element is present at index " + str(found)

Output

element is present at index 8

Recursive Approach (Using Recursion):

def Binary_search(arr,start_index,last_index,element):
	mid =(int)(start_index+last_index)/2
 
	if(start_index>last_index):
		print "Element not found"
	
	elif (element>arr[mid]):
		start_index = mid+1
		Binary_search(arr,start_index,last_index,element)
 
	elif (element<arr[mid]):
		last_index = mid-1
		Binary_search(arr,start_index,last_index,element)
 
	else:
		print "element is present at index " + str(mid)
	
arr = [2,14,19,21,99,210,512,1028,4443,5110]
element = 99
start_index = 0
last_index = len(arr)-1
Binary_search(arr,start_index,last_index,element)

Output

element is present at index 4

Comment down If You have any doubts.