This article is part of a series about tech interview. Go to Tech interview to read more.

⚠️ Since you are here I imagine that have a previous knowledge about programming, and programming language. If you don't know anything about this, maybe this article is not for you yet.

Binary Search: an overview

Today is Jane Doe birthday, you need to call her. You have at your hands a agenda with a lot of names, and phone numbers. If you go for alphabetical order, this will take quite some time. You need to go throw the entire list of names on A, B, C, yeah, you got it.

You need to reduce the time need for that, and that is what the binary search is about. If you open the agenda and check the middle name, you can decide if you want to check names after that, or below that, only at this small change you will reduce the time at half.

Doing this operation again, you will take half of the remaining half. A lot faster, but how much?

The first example you need to check the entire agenda, this is what we call a sequential search resulting in $O(n)$ solution.

The binary search has a $O(\log{}n)$ at the worst case.

Just some quick comparation between both algorithms, where I add the value for n and the amount of steps:

Implementation in Java

We start with the entire list of values:

var low = 0;
var high = sortedList.size() - 1;

After that we check the value at the middle:

int middle = (low + high) / 2;
var item = sortedList.get(middle);

Now we just need to decide if this value is higher, or lower than the one we are searching and continue from that. Now with the full code:

public int search(List<Integer> sortedList, int target) {
    var low = 0;
    var high = sortedList.size() - 1;

    while (low <= high) {
        int middle = (low + high) / 2;
        var item = sortedList.get(middle);

        if (item.equals(target)) {
            return middle;
        }

        if (item.compareTo(target) < 0) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }

    return -1;
}

You can check the same code using generics at my GitHub.

Problems

Ops this section is in progress. 🤪