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:

--

--

--

Student at Flatiron School

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Guild master — Is that a real job title?

Apptainer v1.0.0 Release!

CDAP new landing page

Approach to flaky E2E tests at Clark

K-way Merge

AMA with Chainlink

A note on the problem of not being able to clone in GitLab

Swift. Copy-On-Write

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
anil gurung

anil gurung

Student at Flatiron School

More from Medium

Factory Method Pattern: Let Subclasses decide

Range Sum Query 2D — Immutable

The Basics of Application Memory Management

memory ram

814. Binary Tree Pruning 🚀