Binary Search Algorithms: Overview, When to Use, and Examples

The Linear Search Approach

A linear, or sequential search, is a way to find an element in a list by looking for the element sequentially until the search succeeds. Of course, there are other, better search algorithms available, but linear search algorithms are easy to set up and conduct, so it’s a decent choice if the element list (or array) is small.

Here’s an example of a linear search. Say you have ten buckets, numbered 1-10, and one of them has a tennis ball. You start by looking into Bucket One and see if the ball is in there. If not, then move on to Bucket Two, and keep going in numerical sequence until you finally find the ball. That’s a linear search approach.

So linear searches are straightforward, and you can launch into one with little to no preparation. That's great, but it's slightly less great if you had 1,000 buckets! So that's why we have binary searches.

Watch this video to understand what are binary search algorithms and its applications in data structures.

The Binary Search Approach

Binary searches are efficient algorithms based on the concept of “divide and conquer” that improves the search by recursively dividing the array in half until you either find the element or the list gets narrowed down to one piece that doesn’t match the needed element.

Binary searches work under the principle of using the sorted information in the array to reduce the time complexity to zero (Log n). Here are the binary search approach’s basic steps:

• Begin with an interval that covers the entire array
• If the search key value is less than the middle-interval item, narrow the interval to that lower half. Otherwise, narrow the interval to the upper half.
• Keep checking the chosen interval until either the value is found or the interval’s empty

When to Use Binary Search

Would you be surprised to know that we perform binary searches every day of our lives? Binary searches are highly intuitive and frequently pop up in real life. We'll discuss some examples later.

Although binary search algorithms are typically used to find one element in a sorted sequence, they have many other uses. You can apply a binary search to a result, for example.

Say you wanted to determine the minimum square footage of office space needed to fit all a company's employees easily. Then, you can conduct a binary search for that suggested size rather than sequentially checking through all the possible dimensions. Typically, you would estimate maximum and minimum sizes when conducting the binary search, then check a middle value, so you can halve the interval repeatedly until you get your answer. This process saves a lot of time, especially when considering the vast number of possible iterations of office space square foot available!

There are many other valuable examples, such as code testing, exams, technical recruiting interviews, code challenges, and library tasks.

Implementation of a Binary Search

There are two forms of binary search implementation: Iterative and Recursive Methods. The most significant difference between the two methods is the Recursive Method has an O(logN) space complexity, while the Iterative Method uses O(1). So, although the recursive version is easier to implement, the iterative approach is more efficient.

Iterative algorithms repeat a specific statement set a given number of times. The algorithm uses looping statements (e.g., loop, while loop, do-while loop) to repeat the same steps several times.

On the other hand, recursive algorithms rely on a function that calls itself repeatedly until it reaches the base condition (also called the stopping condition).

Here Is a Sample of Iterative Algorithm Coding

class BinarySearch

{

public static int binarySearchIterative(int[] list, int first, int last, int key)

{

     while(first <= last)

     {

         int middle = first + (last - first) / 2;

            if(list[middle] ==  key)

         {

             return middle;

         }

         else if(list[middle] < key)

         {

             first = middle + 1;

         }

         else

         {

             last  = middle - 1;

         }

     }

     return -1;

}

public static void main(String[] args)

{

     int[] list = {10, 14, 19, 26, 27, 31, 33, 35, 42, 44};

     int element = 31;

     int result = binarySearchIterative(list, 0, list.length - 1, element);

     if(result == -1)

     {

            System.out.println("The element does not exist in the list");

     }

     else

     {

            System.out.println("The element found at index : " + result);

     }

}

}

And Here Is a Sample of Recursive Algorithm Coding

class BinarySearch

{

public static int binarySearchRecursive(int[] list, int first, int last, int key)

{

     if(first >= last)

     {

         return -1;

     }

     int middle = first + (last - first) / 2;

     if(list[middle] == key)

     {

        return middle;

     }

     else if(list[middle] < key)

     {

         first = middle + 1;

         return binarySearchRecursive(list, first, last, key);

     }   

     else

     {

         last  = middle - 1;

        return binarySearchRecursive(list, first, last, key);

     }

}

public static void main(String[] args)

{

     int[] list = {10, 14, 19, 26, 27, 31, 33, 35, 42, 44};

     int element = 31;

     int result = binarySearchRecursive(list, 0, list.length - 1, element);

     if(result == -1)

     {

            System.out.println("The element does not exist in the list");

     }

     else

     {

            System.out.println("The element found at index : " + result);

     }

}

}

Both code samples were provided courtesy of Level Up Coding.

You can employ either method, depending on your needs and situation. Both ways can handle the job efficiently.

Examples of Binary Searches

There's a good reason why some folks refer to binary search algorithms as “the algorithm of everyday life.” Even if you’re not working in an IT-related career, it’s a safe bet that you have routinely performed binary searches. It’s practically automatic! Here are some everyday binary search examples.

Dictionaries

So you somehow find yourself without Internet access, and you need to look up the definition of the word “wombat.” That means behaving like our primitive ancestors would and reaching for an actual physical dictionary! If you wanted to do a linear search, you would start at the “A” words and work your way through the dictionary until you got to “wombat.” Good luck with that!

However, most of us are cleverer than that, and we instinctively employ the binary search method. We consult the “W” listings and go to the middle of that section. If “wombat” is alphabetically smaller than the word on that middle page, we ignore the rest of the pages on the right side. If “wombat” is larger, then we ignore the left-hand pages. We then keep repeating the process until we find the word.

Going to the Library

Here's another use that somehow involves a lack of Internet access. You visit your local library to find a book called "Soups I Have Known." You will be there forever if you enter the library and search the shelves linearly. So, instead, you rely on alphabetization or a code system like the Dewey Decimal System to narrow your search.

Page Numbers

So you've found "Soups I Have Known" and checked it out from the library. A friend told you that there's a fantastic soup on page 200. So you don't open the book to the Foreword and begin turning the pages, working your way up to 200! Instead, you open the book to a random spot and check the page number (we guess this book doesn't have a Table of Contents!). If the page number is greater than 200, then your soup is on the left-hand side of the current page. However, if the page number is less than 200, you turn to the pages on the right-hand side. You keep doing this until you find page 200.

This example is probably the most common, and most of us do it without even thinking about it.

So, whether you’re working as a Data Analyst and trying to implement algorithms, or just an average non-IT person who likes to read but somehow doesn’t have Internet access, binary search algorithms are the way to go!

Do You Want to Know More About Data Structure Algorithms?

Algorithms are heavily used in many IT careers that focus on data analysis and processing. If you're considering a new career in data analysis or a related field, you should become familiar with algorithms. It could even be a difference-maker when you're looking for a job in those fields!

Simplilearn offers a free Introduction to Sorting Algorithms online course. Through this course, you will explore the different types of sorting, the core concepts of sorting, and why these are required. Once you're finished with this course, you will have a clear-cut picture of Bubble Sort, Binary Search, QuickSort, and many more algorithms through relevant practical examples.

You will learn:

• The fundamentals of sorting data structures
• How to pick the relevant algorithm for different scenarios
• How to work with different types of sorting algorithms

This course is ideal for:

• Aspiring software developers
• Data analysts
• Data scientists
• AI engineers
• Coders
• Programming enthusiasts

So, check out Simplilearn and boost your skill set. Who knows? Maybe after learning about algorithms, you can take one of the more intensive courses that build off the free course, like Data Scientist or Data Analyst. Visit Simplilearn today!