Lately I’ve been all in on the job hunt. I’ve been tweaking my resume and LinkedIn. I’ve been thinking deeply about who I am and what I bring to the table for a potential employer, and how I might best express that in an interview conversation. I’ve been attending events and trying to get involved in the local community as best I can. I’ve been coding away on a number of silly little projects. I feel ready to start applying for jobs, except for one little thing…

The technical interview. Interviewing is hard enough, but knowing myself, I am terrible at performing on the spot. My thinking freezes up. Then you throw in the anecdotes that technical interviews are all around stressful and are meant to push you to your breaking point… well, I feel a bit intimidated.

So I’ve been preparing the best way I know how. Studying and practicing technical interview stuff until it feels routine. Taking in as much information as possible. Basically I’m trying to cram a semester of data structures and algorithms into my head. I still don’t feel ready at all, but I thought that it might help me cement some concepts by trying to explain them here.

Binary Search

Let’s start with the good ole’ binary search algorithm. Binary search is one approach to the problem “How do you find something in a sorted array?”. Note the word SORTED, that is key here.

To use binary search, you start in the middle of your array, then compare that item’s value to the value that you’re looking for. Is it bigger or smaller than your target? Whichever it is, you now know which half of the array you need to search next. With this, you’ve effectively cut the number of items you need to search in half. You continue along in this fashion, repeatedly comparing values and eliminating options until you come to your value (or not!).

A real world example of using the Binary Search Algorithm is when you go up to pick up a graded assignment from your teacher’s desk. They’ve sorted all the assignments alphabetically by last name. My last name is “Tran”, so in order to find my assignment I’d check the stack somewhere in the middle, perhaps see that where I’ve stopped is “Hall”, and then I’d limit my search to the second half of the stack. Then I’d check a random spot in this stack, and see “Vick”, and realize that I went too far. And on, and on, until I got to my paper.

Time Considerations

The worst case scenario for searching a sorted array would be O(n), where n is the number of items in the list. This is assuming that you have to check every single item in the list to find what you’re looking for.

Using binary search, every time you check the array, you’re splitting the problem in half. This results in a time cost of O(log n), also expressed in shorthand as O(lg n), which I don’t understand how saving the time of “o” is really all that big of a time save, but so it is…

Further Resources

Learn set me up with a subscription to InterviewCake, and I’ve found it helpful so far. Their intro page on Binary Search includes links to relevant practice problems at the bottom.