Discover data structures and algorithms using Python. Gain insights into solving real-world problems and typical interview questions with detailed reviews, explanations, and hands-on coding exercises.

Data structures and algorithms are among the most fundamental concepts of Computer Science. Whether it’s real-world problems you’re trying to solve or the typical coding question asked in an interview, almost every problem requires you to demonstrate a deep understanding of data structures and algorithms. 

This course is a detailed review of some of the most common data structures and algorithms that you’ll see in interviews and your everyday work. With implementation details, thorough explanations, and hands-on coding exercises, you’ll quickly gain the confidence you need to solve any problem, no matter the situation.

Data Structures and Algorithms in Python

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

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:

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)$.


This is where binary search comes into play. Binary search is more efficient than the linear search. Let's find out how. 

# Binary Search (Iterative)
Binary search assumes that the array on which the search will take place is sorted in ascending order. In binary search, the target element is compared with the middle element of the array following which the next chunk of the array to be searched is decided. If the target matches the middle element, we are successful. Otherwise, since the array is sorted, if the target is smaller than the middle element, it could only be in the left half of the array. Alternatively, if the target is greater than the middle element, it could be in the right half of the array. So, we exclude one half of the array from the further search and repeat the same strategy to the remaining half.

Let's jump to the code below so you get a clearer idea of binary search. 

In this lesson, you will learn about the Binary Search algorithm and its implementation in Python. 

Introduction

Stack

Singly Linked Lists

Circular Linked Lists

Doubly Linked Lists

Arrays

Binary Trees

Binary Search Trees

Binary Search

Recursion

String Processing

Binary Search

Linear Search