Modified Binary Search

In this blog post, I will be giving a brief description on another important data structure that is very important for technical interview. This data structure is called Modified Binary Search. This pattern is very useful to solve problems that includes a sorted array, linked list, or matrix , and we are asked to find a certain element. This pattern describes an efficient way to handle all problems involving Binary Search.

The pattern looks like this for an ascending order set;

Let’s assume that start is the first element and end is the last element in an array named arr. So,

start = 0

end = arr.length -1

Now, we start by finding the middle value (mid) of start and end. An easy way to find the middle value would be:

mid = (start + end) / 2.

But this has a good chance of producing an integer overflow , so it’ is recommended that we represent the mid value as:

mid = start + (end — start) /2

If the key is equal to the number at index mid then we return mid as the required index.

But, if ‘key’ is not equal to the index mid, then there are two possibilities that we need to check;

1. If key<arr[mid], then we can conclude that key will be smaller than all the numbers after index mid as the array is sorted in the ascending order. We can reduce our search to end = mid -1
2. If key>arr[mid], then we can conclude that key will be greater than all the numbers after index mid as the array is sorted in the ascending order. We can reduce our search to start = mid +1

For example;

Let us suppose that we have an array named arr = [1,2,3,4,5,6,7] and we have to search the key number that is 5 and find its index.

source: hackernoon.com

References:

14 Patterns to Ace Any Coding Interview Question