Nerd For Tech
Published in

Nerd For Tech

Binary Search

A binary search is an algorithm that finds a given target in a sorted array. The binary search algorithm compares the target to the middle element of the array. Assuming the target is not the middle element you will compare whether the target is larger or smaller than the middle element. If the target is larger then you will ignore the elements to the left and go through finding the middle element of the remaining half. The same is true if the element is smaller except you ignore the elements to the right. This process is then repeated until the target is found or you run out of options and determine the target is not in the array.

Example

Given the numbers, 1 through 10 find the number 6. To start we will go to the middle number 5. The number 5 is less than 6 so we will ignore the numbers to the left of 5.

With the remaining numbers, we will go to the middle number 7. The number 7 is greater than 6 so we will ignore the numbers to the right.

Again going to the middle of the remaining numbers we arrive at the number 6. The number 6 is equal to 6 and so you know you have found the target.

This algorithm has a time complexity of O(log n) because each search is reducing the number of elements you will need to search by half.

Code Implementation

The LeetCode problem called Binary Search deals with this problem.

To implement binary search you will create a variable to hold the left and right values of the array. Initially left is 0 and the right is the length of the array minus 1.

Create a while loop that will loop while the left variable is less than or equal to the right variable. You will also create a new variable that will hold the middle value of the array. To get the middle of the array we can add the left and right variables together and then divide them by 2.

Now if the element in the middle is less than the target you will set the left variable to the middle variable plus one because we already know the middle is not the target.

If the element in the middle is greater than the target you will set the right variable to the middle variable minus one.

If we make it past both of the if statements we can return the middle variable because it is the target.

And if the while loop ends and the middle variable is not returned then we know the target was not in the array. In the LeetCode example, we are instructed to return -1.

Integer Overflow

There is a small improvement you can make to this code. If the array is large enough, the left and right variables may exceed the 32-bit integer max and overflow when adding them together. This would give you an incorrect middle number. A way around this is to calculate the distance between the left and right variables and divide that number by 2. You can then add this number to the left variable to get the middle number.

--

--

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