Search⌘ K
Home
Courses
Data Structures and Algorithms in Python

Binary Search

Explore the binary search algorithm in Python to efficiently find target elements in sorted arrays. Understand and implement both iterative and recursive approaches, and compare their efficiencies against linear search. This lesson enhances your problem-solving skills by teaching a fundamental search technique widely used in coding interviews and algorithmic challenges.

We'll cover the following...

In this lesson, we take a look at the well-known Binary Search algorithm in Python. Binary Search is a technique that allows you to search an ordered list of elements using a divide-and-conquer strategy. It’s also an algorithm you’ll want to know very well before you step into your technical interview. Now before we dive into discussing binary search, let’s talk about linear search.

Linear search is when you iterate through an array looking for your target element. Essentially, it means sequentially scanning all the elements in the array one by one until you find your target element.

Let’s see how we do this in Python:

Python 3.5
def linear_search(data, target):	
	for i in range(len(data)):
		if data[i] == target:
			return True
	return False

The for loop on line 2 starts from i equal 0 and runs until i equal len(data) - 1. If in any iteration data[i] equals target, we return True to indicate that we have found target in data. On the other hand, if the for loop terminates and the condition on line 3 never comes out to be True, False is returned from the function (line 5). In the worst case, we might have to scan an entire array and not find what we are looking for. Thus, the worst-case runtime of a linear search would be O(n)O(n) ...