Binary Search in Python and Methods [With Code Examples]

Introduction to Binary Search Algorithm

This article will teach you how to use the Binary Search sort. Working examples of Binary Search in Python can also be found.

Binary Search is a search algorithm for determining the position of an element in a sorted array. The element is always searched in the middle of a part of an array in this method. Only a sorted list of things can be used for binary search. We must first sort the elements if they are not already sorted.

The Binary Search Algorithm can be implemented in two different methods.

  1. Iterative Process
  2. Method of Recursion

Undersating of Binary Search Methods and Code Examples

Write a function to search a sorted array arr[] of n elements for a given element x. A linear search is a straightforward method. The above algorithm has an O time complexity (n). Binary Search is another method for accomplishing the same goal.

Binary Search: Divide the search interval in half periodically to search a sorted array. Create an interval that spans the full array to begin. The interval should be restricted to the lower half of the search key’s value is less than the item at the interval’s midpoint. Otherwise, limit it to the upper half of the page. Check the value until it is discovered or the interval is empty.

The binary search aims to take advantage of the fact that the array is sorted in order to minimize the time complexity to O. (Log n).

After just one comparison, we virtually disregard half of the elements.

  • The center element should be compared to x.
  • If x matches the middle element, we return the mid index.
  • Else If x is greater than the mid element, it can only be found in the right half subarray after the mid element. As a result, the process is repeated for the right half.
  • Otherwise, continue with the left half (x is smaller).

Now let’s have to code examples:

Example 01: Code of recursive binary search.

# Code recursive binary search.
def binarySearchAlgorithm(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) 
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binarySearch(arr, l, mid-1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	else:
		return -1
arr = [3, 43, 56, 96]
find = 56
result = binarySearchAlgorithm(arr, 0, len(arr)-1, find)
if result != -1:
	print("Element is present at index % d" % result)
else:
	print("Element is not present in array")

Output:

img1

Example 02: Code to implement iterative Binary Search.

# code to implement iterative Binary Search.
def binarySearchIterative(arr, l, r, x):
	while l <= r:
		mid = l + (r - l) // 2;
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1
arr = [ 4, 9, 8, 20, 80 ]
find = 80
result = binarySearchIterative(arr, 0, len(arr)-1, find)
if result != -1:
	print ("Element is present at index % d" % result)
else:
	print ("Element is not present in array")

Output:

img2

General Approach

  • Calculate the first power of two that is larger or equal to the array’s size.
  • Create an index with a value of 0.
  • While the computed power is larger than 0, divide it by 2 each time.
  • When the element at position [index + power] = target, the power value is added to the index variable. (Compute the total)
  • Check if the element at location [index] == target after the for loops. If so, the target element is in the array; else, it isn’t.

Time Complexity

T(n) = T(n/2) + c = T(n) = T(n/2) + c = T(n) = T(n) = T(n) = T(n) = T(n) = T(n)

The Recurrence Tree approach or the Master method can be used to solve the aforementioned recurrence. It belongs to the Master Method’s Case II, and the recurrence’s answer is.

In the case of iterative implementation, Auxiliary Space is O(1). O(Logn) recursion call stack space in the case of recursive implementation.

We’re going to use

mid = low + (high – low)/2; int mid = low + (high – low)/2;

Perhaps you’re wondering why we calculate the middle index this way when we could just add the lower and higher indexes and divide them by two.

int mid = (low + high)/2; int mid = (low + high)/2; int mid = (low + high)/2;

However, calculating the middle index in this manner indicates that our code is not error-free and contains defects.

That is, for greater values of the int variables low and high, it fails. If the sum of low and high is more than the maximum positive int value(231 – 1), it fails.

When the sum exceeds a negative value, the value remains negative when split by two. It throws an ArrayIndexOutOfBoundException in Java.

mid = low + (high – low)/2; int mid = low + (high – low)/2;

As a result, it’s preferable to use it in this manner. This flaw affects merge sort and other divide-and-conquer algorithms alike.

That’s all for this article. If you have any confusion contact us through our website or email us at [email protected] or by using LinkedIn.

Suggested Articles:

  1. What is Hashmap in Python?

Leave a Comment