Introduction to Binary Search and Complexity Analysis with Python

Part 1 of "Data Structures and Algorithms in Python"

Data Structures and Algorithms in Python is beginner-friendly introduction to common data structures (linked lists, stacks, queues, graphs) and algorithms (search, sorting, recursion, dynamic programming) in Python, designed to help you prepare for coding interviews and assessments. Check out the full series here:

Binary Search and Complexity Analysis
Python Classes and Linked Lists
Arrays, Stacks, Queues and Strings (coming soon)
Binary Search Trees and Hash Tables (coming soon)
Insertion Sort, Merge Sort and Divide-and-Conquer (coming soon)
Quicksort, Partitions and Average-case Complexity (coming soon)
Recursion, Backtracking and Dynamic Programming (coming soon)
Knapsack, Subsequence and Matrix Problems (coming soon)
Graphs, Breadth-First Search and Depth-First Search (coming soon)
Shortest Paths, Spanning Trees & Topological Sorting (coming soon)
Disjoint Sets and the Union Find Algorithm (coming soon)
Interview Questions, Tips & Practical Advice (coming soon)

You can earn a verified certificate of accomplishment for this course by signing up here: http://pythondsa.com .

Be sure to check out the community forum for asking questions, getting help and participating discussions with other course participants: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/78

How to Run the Code

The best way to learn the material is to execute the code and experiment with it yourself. This tutorial is an executable Jupyter notebook. You can run this tutorial and experiment with the code examples in a couple of ways: using free online resources (recommended) or on your computer.

Option 1: Running using free online resources (1-click, recommended)

The easiest way to start executing the code is to click the Run button at the top of this page and select Run on Binder. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

Option 2: Running on your computer locally

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

Jupyter Notebooks: This notebook is made of cells. Each cell can contain code written in Python or explanations in plain English. You can execute code cells and view the results instantly within the notebook. Jupyter is a powerful platform for experimentation and analysis. Don't be afraid to mess around with the code & break things - you'll learn a lot by encountering and fixing errors. You can use the "Kernel > Restart & Clear Output" menu option to clear all outputs and start again from the top.

Why You Should Learn Data Structures and Algorithms

Whether you're pursuing a career in software development or data science, it's almost certain that you'll be asked to solve programming problems like reversing a linked list or balancing a binary tree in a technical interview or coding assessment.

It's well known, however, that you will almost never face these problems in your job as a software developer. So it's reasonable to wonder why such problems are asked in interviews and coding assessments. Solving programming problems demonstrates the following traits:

You can think about a problem systematically and solve it systematically step-by-step.
You can envision different inputs, outputs, and edge cases for programs you write.
You can communicate your ideas clearly to co-workers and incorporate their suggestions.
Most importantly, you can convert your thoughts and ideas into working code that's also readable.

It's not your knowledge of specific data structures or algorithms that's tested in an interview, but your approach towards the problem. You may fail to solve the problem and still clear the interview or vice versa. In this course, you will learn the skills to both solve problems and clear interviews successfully.

This course takes a coding-focused approach towards learning. In each notebook, we'll focus on solving one problem, and learn the right techniques, algorithms, and data structures to come up with an efficient solution to the problem. We will also discuss how the technique can be applied to solve other similar problems.

Problem

In this tutorial, focus on solving the following problem:

QUESTION 1: Alice has some cards with numbers written on them. She arranges the cards in decreasing order, and lays them out face down in a sequence on a table. She challenges Bob to pick out the card containing a given number by turning over as few cards as possible. Write a function to help Bob locate the card.

This may seem like a simple problem, especially if you're familiar with the concept of binary search, but the strategy and technique we learning here will be widely applicable, and we'll soon use it to solve harder problems.

The Method

Upon reading the problem, you may get some ideas on how to solve it and your first instinct might be to start writing code. This, however, is not the optimal strategy, and you may end up spending a far longer time trying to solve the problem than you might anticipate, or you may not be able to solve it at all.

Here's a systematic strategy we'll apply for solving problems:

State the problem clearly. Identify the input & output formats.
Come up with some example inputs & outputs. Try to cover all edge cases.
Come up with a correct solution for the problem. State it in plain English.
Implement the solution and test it using example inputs. Fix bugs, if any.
Analyze the algorithm's complexity and identify inefficiencies, if any.
Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

"Applying the right technique" is where the knowledge of common data structures and algorithms comes in handy.

Use this template for solving problems by applying this method: https://jovian.ai/aakashns/python-problem-solving-template