How to BS (binary search) the CS

Throughout my CS journey, I found it’s sometimes difficult to remember certain algorithms or data structures. Sometimes an algorithm can be very complex and you might forget some important steps, especially under the pressure of a coding interview.

Most people when they are facing an unknown challenge they tend to freak out, which is normal but hopefully after you read this you will be much more confident when you are facing a new challenge.

If you are facing a problem that takes crucial thinking, there are a few guidelines that can help you. Everyone learns differently, certain techniques that are mentioned may work for you when others don’t.

Step 1 — Assess your current knowledge on the topic.

When you face a problem, take a step back and analyze the problem.

The University of Indiana did a study on a group of students and discovered some interesting ways to improve your learning process by using some learning techniques that help to analyze the situation. Start by asking questions: what do you know about the topic? Do you see any patterns?

Elaborative Interrogation is a great technique to start your thinking process.

Step 2 — Draw/write the problem out.

Have you heard or seen that famous quote that has been circling around “To accomplish great things, we must not only act but also dream, not only plan but also believe”. Having an image or drawing or writing of the problem helps to understand and come up with some strategies.

Step 3 — Talk it out.

For most people when it comes to critical thinking tend to analyze possible solutions in their minds, which most of the time can get you stuck in an endless loop of thoughts that could lead to confusion. Speaking your thought process and pseudo-coding it comes in handy in the process of implementing a solution to solve the problem. It also shows that you have a good intellectual foundation of problem-solving and has the potential to be an asset to the company during a technical interview.

Step 4 — Break it down.

Just like how we are doing right now, take it step by step.

Start from the basics (the genesis of your implementation) to best re-evaluate the implementation plan and work the problem, while avoiding the risk of edge cases (involuntary mistakes).

Let’s Jump Into It

A good technique I use to remind myself of search or recursion algorithms is to associate them with common material items.

Iteration & Recursion

Iteration is the act of repeating a process, either to generate an unbounded sequence of outcomes, or with the aim of approaching a desired target. Each repetition of the process is called ‘Iteration’. The result of one iteration are used as the starting point for the next iteration.

A typical pattern for assignment is an assignment that updates an variable — where the new value depends on the old. A common case is when you are going up the stairs, while climbing up the stairs you go step by step without skipping a step, updating a variable by adding one is called increment, and if you going down the stairs which you will be subtracting by one is called decrement.

Recursion is a method where the solution to a problem depends on smaller instances of the same problem (as opposed to iteration). Always remember to check your base case, which consist of checking the base case of your problem, before making a recursive call.

A common recursion action we do in our daily basis is when your a counting a quantity of boxes you start from the beginning to the end, but in order to verify you count you also count from the end to the beginning.

Selection Sort

The idea of this algorithm is to find the smallest element in the unsorted list and swap it the beginning of the sorted list.

Let’s pseudo:

Imagine you just finished doing laundry, and while you are folding your clothes you found 8 different pairs of socks with different sizes 1 to 12 but you find them unsorted [ 5, 7, 1, 8, 5, 2, 12] all over your bedroom floor, now you need to pick them up so you can put them in your closet. You start with the first sock that is in front of you. The first sock you picked up was sock number 5 and assuming that the first sock you got is sorted, look on the floor for the smallest socks size that you see in front of you, in this case, number 1, now compare if the one you picked up is greater or less than the one you had before, if the number it’s less you swap the smallest size value to the first sock you picked up. Once that is done you get the next sock in front of you 7, check again for the smallest socks size that you see in front of you, which will be 2, is 2 <7? Yes! So swap the smallest size for the current size being compared [1, 2, 5, 8, 5, 12]. Keep looping through the socks until everything it’s sorted. Remember a sorted list is in ascending order which means the lower numbers stay on the left side and greater numbers towards the right side.

Bubble Sort

The idea of this algorithm is to move the greater values generally towards the right and the lowest values generally towards the left.

Let’s pseudo:

Imagine that you are in a library and you are looking for a certain Harry Potter book but it’s very hard for you to find the book that you are looking for because the bookshelf is very messy and not in order [1, 4, 5, 2, 6, 3 , 7], so you decide to organize it by the volume of each book smallest books towards the left and bigger books towards the right.

So first you look through the beginning of the bookshelf and compare the first and the second book to each other, is 1 > 4? No! So it means that first element in that list is already sorted, so now compare the next pair, is 4 > 5? No! So compare the next pair, is 5 > 2? Yes! So now you swap them [1, 4, 2, 5, 6, 3, 7], and you keep going looping thought until all the books are sorted [1, 2, 3, 4, 5, 6, 7].

Insertion Sort

The idea behind this algorithm is to build your sorted array in place, shifting elements out of the way if necessary to make room as you go.

Let’s pseudo:

It’s Friday night and you and your friends are celebrating the weekend and having a good time. Your friends decided to play Uno, as the game is starting you get a quantity of 7 cards, as you are analyzing your cards you notice that they are not in order [5, 7, 2, 4, 3, 8, 9], to rearrange your cards you start from the very beginning, your card first we will set as if it is sorted, now look at the next unsorted card, and now insert it to the sorted portion by shifting the requisite number of cards.

Linear Search

The idea of this algorithm is to iterate across the array from left to right, searching for a specific element.

Let’s pseudo:

So imagine you are getting ready to go out, but you are looking for your favorite shirt so you can match with the rest of your outfit, you look through your closet shirt by shirt, if you find the shirt you are looking for stop, otherwise, keep going through your closet.

Binary Search

The idea behind this algorithm is that you divide in half and compare if one of the halves is greater or lower than the item that you are looking for.

Let’s pseudo:

You are looking for the definition of a word in a dictionary, a dictionary is always sorted in alphabetical order, let’s say that you are looking for the word Rainbow, so you go the middle of the dictionary and you get the letter G, if R (which is the first letter of the word we are looking for) is < (lower) than G we go left and if is > (greater) we move right. In this case is greater so we discard the left side and go toward the middle of the right portion and repeat the operation until you find the word RAINBOW.

Summary

These are some simple daily habits that we do that are a form of search algorithms, associating these habits will help you understand better what it’s going on in your own problem, and remember to follow all 4 steps. If you want to dive in more in these topics, I will leave a list of good resources. Thank you so much for your time and if you want to read more about some interesting topics stay tuned!

Great follow-up resources:
Ones and Zeros, the Magic Heroes that Make the World Go ‘Round
Github Recursive Complexity Equations
Github Coding interview University
Cracking the Coding Interview, 6th Edition
Review Make School’s algorithm analysis slides
Read Interview Cake’s article on the idea behind big O notation
Read Interview Cake’s article on logarithms and binary search
Watch HackerRank’s recursive algorithms video, binary search algorithm video, and big O notation video
Watch Harvard’s old recursion video, new recursion video, stack frames video, linear search video, binary search video, asymptotic notation video, and computational complexity video
Title created by TJ King
Code pumpkin
Tutorials Point