Binary Search

Algorithms: Binary Search, Revisted

- Tracy Leave a comment

A while back I walked through the basic idea of binary search. Knowing what binary search is, and implementing it however, are very very different things.

I’ve been taking a technical interviewing course, in order to add some sort of method to the madness of my job hunt. Pretty much every day we’re whiteboarding and mock interviewing. Last night I received the following question while I stood at the whiteboard:

Number of Ones
Given a sorted bit array (values of 0, and 1) determine the number of 1’s in the array.

Input: Array of elements with values belong to the set S : { 0, 1 }
Output: Integer
Example
Input: [0, 0, 0, 1, 1, 1] => Output: 3
Input: [0, 0, 0, 0] => Output: 0

Constraints
Time Complexity: O(log n) A linear search is not acceptable for runtime.
Auxiliary Space Complexity: O(1)

So, the naive solution here would be to iterate over the entire array, and keep count of how many ones we encounter (or just use Ruby’s built in count method…). But of course to check every item in the array that would be time of O(n). Linear search runtime isn’t acceptable!!!

Several things made my mind jump to binary search. First off, the array is sorted. Second, the very obvious time complexity of O(log n). And also the entire array is binary. Isn’t that cute.

But just because you know what to do doesn’t mean that it will be easy. I decided in my approach to have a “middle_index” that I was moving around throughout the array, but I forgot to implement a start_index and an end_index to keep track of my new subarrays. GAH!!! I kept trying to make only middle_index work until I ran out of time. When I was told about the additional markers, it felt so so obvious to me, and so much simpler. In fact, when I was walking through my diagram of the problem on a test array, my hands were the natural bounds of the start_index and the end_index. It just didn’t register.

Anyways, today I went back and finished up my ruby method for this problem. I almost forgot to account for the two cases that might drive me into an infinite loop: an array of all 0’s or all 1’s. I think it will take me several more runs of this, but hopefully someday implementing binary search will be fast and breezy.

And here’s my general Ruby implementation of Binary Search.

Algorithms: Binary Search

- Tracy 1 Comment

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.

Scroll To Top