Originally posted at Mavention.nl.

Searching. One of the most crucial activities performed on datasets. Think of a world with lots of data, but no possibility to filter relevant info for yourself. Sounds pretty stone-age right? Thankfully we have lots of options to perform the craziest search queries on huge datasets. These options are available to us for quite some time, and we got used to perceiving lots and lots of data. In this digital age we tend to thrive for the most efficient ways to gather data, but besides that: we want it fast. So how do we search through data in a quick way? In this technical blog post I will shine my light on one of the most underrated searching methods: Binary searching. It is one of the quickest ways to retrieve data, but it has its downsides.### Binary searching - The basics

As the name gives away binary searching is about 0 and 1: yes or no, true or false. This method doesn't aim to look for an array item by looping through an array and waiting for it to bounce back a result. Instead, it uses something that looks like a "warmer, colder"-kind of approach. But then without the "colder". Imagine playing a game of hide and seek and you get to ask the person that is hiding to shout their name every 5 seconds. You'll get their location in no time! Binary searching loops through an array by looking for an item and asking the array if it is nearing it. To summarize the method in one sentence:"Search an array by splitting it in half - each iteration."

Let's say we have an array of 10 integers and we're looking for the number 2. Normally we would have to loop through the entire array until the iteration finds '2'. For this number, it will take 3 iterations to get to number 2 (3rd position in the array) but it could also take 11 loops if the number is 10. Binary searching tries to optimize the efficiency of searching this array. Instead of looping through the entire array it splits the array in half each time. It does this by determining a minimum and a maximum. Both variables will change each iteration until the number is just between the two, at which the number has been found.### Binary searching - Code example

In the below example I have created a binary searching method which retrieves an array of integers and a number that it needs to find. It defines a leftIndex (the index of the minimum position it needs to look at) and a maxIndex (which is always the length of an array minus one). It will iterate with the condition that the minimum index plus one needs to be smaller than the maxIndex. This will prevent us from looping outside of the array (in case we're looking for number 11). Inside the loop, we define between what positions we need to check. Then we split that up by dividing by 2. Finally, we will define the current position we're looking at which is the minimum plus the (max) position of the divided variable (lookTill). We check its value with the given number and decide if it is bigger than or smaller than the current value. Inside the if else statement we basically tell our method to move to the left or to the right by determining the minimum and maximum look up positions. However, if the current number is the number we're looking for there is no need to iterate any further!private static bool FindNumberNormallyInArrayBinaryStyle(int number) { int leftIndex = -1; int maxIndex = nums.Length-1; while (leftIndex + 1 < maxIndex) { nonRecursiveBinaryAttempts++; int lookBetween = maxIndex - leftIndex; int lookTill = lookBetween / 2; int lookAt = leftIndex + lookTill; long currentValue = nums[lookAt]; if (currentValue > number) { maxIndex = lookAt; } else { leftIndex = lookAt; } if (currentValue == number) { return true; } } return false; }

### Binary searching - To recurse or not to recurse

The above example demonstrates how to use binary searching without using recursion. But perhaps we could make this code cleaner, more efficient or just way more awesome by using recursion (another recursion example here)! The below code shows how to make it recursive.private static bool FindNumberRecursivelyInArrayBinaryStyle(int number, int leftIndex, int maxIndex) { if (leftIndex + 1 < maxIndex) { recursiveBinaryAttempts++; int lookBetween = maxIndex - leftIndex; int lookTill = lookBetween / 2; int lookAt = leftIndex + lookTill; long currentValue = nums[lookAt]; if (currentValue > number) { maxIndex = lookAt; } else { leftIndex = lookAt; } if (currentValue == number) { return true; } else { return FindNumberRecursivelyInArrayBinaryStyle(number, leftIndex, maxIndex); } } else { return false; } }