Brute Force, Binary Search and Time Complexity

Problem

In this notebook, we 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.

Method to solve DSA problem

1. State the problem clearly and identify inputs and outputs.
2. write down some tests inputs and outputs and most importantly cover all edge cases.
3. Write a solution (In plain English and in coding).
4. Test the example inputs and outputs.
5. Fix bugs and repeat step 3 to 4.

(Problem Solved)

6. Analyze algorithm's complexity and Identigy Ineffficiencies, if any.
7. Overcome inefficiencies

Solution

Step1: State the problem clearly and identify inputs and outputs

Alice has cards with numbers arranged in decreasing order.
She asks bob to draw a card with specific number.
It has to be done in minimum possible drawing.

Inputs: list of cards arranged in decreasing order, a number of card to be drawn
Output: Index of the card

Step2: Test inputs and outputs

1. general case: list of different cards with a card to be drawn (not edge cards)
2. same as above but edge cards to be drawn
3. list has recurring cards non-recurring cards to be drawn (not edge cards)
4. same but recurring cards to be drawn
5. list is empty (impractical in reality but practical for code)
6. all recurring cards in list
7. a card to be drawn which is not in list