Binary Search
In the previous blog post, I defined the brute force & provided an example. I also pointed out that brute force isn’t the best way to solve algorithm questions. This time we’ll be talking about an approach which is a lot more efficient: Binary Search.
Let’s assume you are reading a book, and run into a word that you have never heard of before: Mellifluous. You decide to look up the word in the dictionary where all the pages are sorted(ascending order).
One way you can do it is by looking at every single page until you come across the one that has our word on it (brute force). Another way would be going straight to the middle and deciding whether mellifluous comes before or after the middle page. If it comes before, then you’ll go halfway towards the beginning. If it comes after, you’ll go halfway towards the end. In either case, you’ll need to divide the search interval in half repeatedly (binary search).
Tree Data Structure
I want to provide some insight into the Tree Data Structure so that it will make more sense when we talk about the Binary Search Tree in the next section.
The collection of elements that have links to each other is called a tree that looks like a tree in nature, with one difference: it’s upside down. The tree is hierarchical, unlike the linear data structures.
Each element in the tree is called a node. A node has the data value itself and a pointer that addresses other nodes. The root node is the starting node; the nodes below it are its child nodes, which also may have their child nodes. This goes on and on.
A node can be both a child and a parent node.
Two nodes that are next to each other are called siblings. Any node that doesn’t have a child is a leaf node. A subtree can be viewed as a complete tree in itself, which is a child of a node.
Binary Tree
A binary tree is a type of tree where every node has a maximum of two immediate children. The nodes can have one child or no child at all, which would make them a leaf node. But they can never have more than two children. The child nodes are referred to as the left child and the right child.
Binary Search Tree
A binary search tree(BST) is a type of binary tree that naturally stays sorted because every right child must always be greater than its parent, and every left child must be less than its parent.
A BST is balanced when its left and right subtrees have roughly the same amount of child nodes, although not necessarily the same amount. If the left and right side of a BST had the same amount of nodes, that would make it a perfect tree, which is quite rare.
In its worst-case scenario, a BST can be so unbalanced that it becomes a degenerate tree, which is a linked list.
Implementation
We have n versions of a product. At a certain point, a bug was introduced, and after that, the bug stayed in our product.
We are asked to return the first bad version, which will be followed by the other bad versions because all the versions after a bad version are bad as well.
We can start by defining three variables for the starting point, ending point, and the middle point to implement a binary search. The starting point should be one as our given array starts at 1, the ending point is going to be n because we are told that there are n versions.
After defining the starting and ending point, we need to create a middle point using these two. We need the midpoint formula: first + (last-first)/2. We are going to wrap that in Math.floor to round it down.
If the middle point isn’t a bad version, the bad version is to the right of it somewhere. So we are setting the first one to middle + 1.
If it is a bad version, any data point to the right of it can’t be the first bad version. So we are eliminating the right side of our data set.
Hopefully, this was helpful!
