Binary search

Property of an ascending sorted array

  1. Every element is bigger than or equal to all the elements on its left side. For instance, 19 in the array below is greater than all the elements on its left side.

Idea

We can exploit this property of a sorted array to optimize our search by reducing our search space to only the region where we are certain to get the target element. Let’s understand this statement by an example: — We are given a sorted array of length n, where we need to search for element 46.

Defining search space

A search space is defined as the region in the array where we are finding the target element. We are going to identify the starting and ending of the search space using two pointers. We will call them ‘start’ and ‘end’. Following are the examples of a valid search space:

Calculating the middle position

Middle index of a search space can be easily calculated using its starting and ending positions.

Step by step iterative implementation

Now that we have covered all the prerequisites, we can start implementing the algorithm. Let’s say we are searching for a target element E.

Example dry run

The following is an algorithm dry run when element to be searched is 19:

Code (C++)

--

--

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