Binary search algorithm

Nov. 28, 2017

Introduction

It is my most favorite algorithm last six months. My last practice was in less than a week ago, and I made a mistake about the edge case.

On Nov. 27, 2017, I had chance to review the peer's binary search algorithm and I gave out some code review.

So interesting to work on mock interview, I like to write more about mock interview in general on binary search algorithm.

Common mistakes in binary search algorithm

Let me choose a topic and then I write something around the topic.


Focus on middle value

One time in mock interview, I did start value checking in the base case, and then later peer told me that I should focus on the middle

value. The depth first search is about base case, about middle value. Write simple code as possible, avoid discuss start value.


Structure your code very well


There are two ways to write binary search algorithm. Either recursive or iterative, the structure of code should be well structured.

Continue to work, kind of loop

Do some work for base case

Some logic checking to reduce the range of search to half


End of loop

Edge case 

Sometime half of range is only one node. In order to include the node into the first half range, the condition should be considered carefully to allow equal sign in comparison. One example is here.

The practice of binary search with the edge case bug is documented in the blog called binary search algorithm is always my favorite.

Converge concern

The binary search is to remove half of nodes every step, the base case is to check if the middle value node is satisfied the condition. In

case the search will not converge, it is better to narrow down the next range as (middle, end] or [start, middle. Exclude middle, at least one node is removed each iteration. There is at most n iteration, where n is the length of the size to search.


References:

Past practice 1: blog is here.