What is Binary Search Algorithm and What are its Uses?

What is Binary Search Algorithm and What are its Uses? | Artificial Intelligence and Machine Learning | Emeritus

What is binary search? To put it simply, it is an efficient algorithm that narrows down a search space by repeatedly dividing it in half. Used primarily to find elements in a sorted array, this algorithm technique is at the root of many tools and applications that industries and individuals use extensively. From finding misspelled words in autocorrect to GPS navigation systems and decision trees used in AI systems, the binary search approach finds its place in various data-intensive, array-based applications. So, what’s the logical structure of the binary search approach, and what are its real-life uses? Let’s explore!

How do Binary Searches Work? 

Binary search is a widely used algorithmic technique. Its function is to find a particular component within a sorted array. This is especially useful in places where mining a particular dataset and making repeated search queries is important. By leveraging the array’s order, the binary search approach halves the search space with every iteration or recursive call, resulting in a time complexity of O(log n). 



Below, you will find two implementations of binary search: iterative and recursive. These codes have been reproduced from Github.

The iterative approach ensures a systematic reduction of the search space, efficiently locating the target or determining its absence in the list. Below is a sample Python code for iterative binary search.

def binary_search(a_list, search_item):

    “””

    Binary search using loop on a sorted list

    Based on the value we are looking for, bifurcate the list into two look-up windows. 

    The value we look for is the middle value of the current window. 

    

    If search value < middle value of the window, put the upper bound to the middle value.

    If search value > middle value of the window, put the lower bound to middle value.

    

    If search value == middle value of the window, item is found.

    If lower bound > upper bound, the list limits are out of index. We can stop the search. 

    “””

    

    low = 0

    high = len(a_list) – 1 

    

    while low <= high:

        mid = (high + low) // 2

        

        if a_list[mid] == search_item:

            return mid + 1

        else:

            if search_item > a_list[mid]:

                low = mid + 1

            else:

                high = mid – 1

    return -1

The logical flow of the iterative binary search:

  • Initialize boundaries: Start with low pointing to the first element and high pointing to the last element of the sorted list
  • Calculate midpoint: Compute the middle element using (high + low) // 2
  • Compare with target: If the middle element is the search item, return its position
  • Adjust search boundaries: If the target is smaller than the middle element, adjust the high pointer to mid – 1, reducing the search space to the left half. If the target is larger, adjust low to mid + 1, shifting the search to the right half
  • Continue until bounds overlap: Repeat the process until low surpasses high, indicating that the item is not present. In that case, return -1

The iterative approach ensures a systematic reduction of the search space, efficiently locating the target or determining its absence in the list.

ALSO READ: 10+ Practical Uses of Artificial Intelligence Across Sectors

An alternative approach to binary search involves recursion, where the problem is broken down into smaller subproblems. Below is the recursive implementation:

def binary_search2(a_list, search_item, low, high):

    “””

    Binary search using recursion.

    “””

    if low <= high:

        mid = (high + low) // 2

        

        if a_list[mid] == search_item:

            return mid + 1

        else:

            if search_item > a_list[mid]:

                return binary_search2(a_list, search_item, mid + 1, high)

            else:

                return binary_search2(a_list, search_item, low, mid – 1)

    return -1

The logical flow of the recursive binary search is explained below:

  • Base condition: The recursion terminates when low exceeds high, indicating the search space has been exhausted
  • Calculate midpoint: As with the iterative method, the middle element is computed as (high + low) // 2
  • Compare with target: If the middle element matches the search item, return its position
  • Recursive search: Depending on whether the target is smaller or larger than the middle element, recursively search the left or right half by adjusting the low or high values accordingly
  • Return result: The recursion continues narrowing down the search space until the item is found or the base condition is met

1. Autocorrect and Spell Check

Autocorrect and spell-check systems rely on binary search to swiftly look up words in massive dictionaries. When you type a word, the system checks it against a predefined, alphabetically listed dictionary. Binary search quickly determines whether the word exists in the dictionary or not. As a result, this process dramatically improves the speed at which the system can suggest corrections or flag errors. In real-time applications like texting or writing emails that today involve natural language processing, this speed is essential for a smooth user experience.

2. Version Control Systems (Git Bisect)

In version control systems like Git, developers often need to find the first commit that introduced a bug. Git’s bisect command uses binary search to efficiently identify the faulty commit. The process begins by marking a “good” commit and a “bad” commit. Then, Git checks a commit in the middle of this range. If the middle commit works fine, the search moves to the newer half of the history. If it’s broken, it searches the older half. This drastically reduces the number of commits a developer needs to check, saving time and effort during debugging.

ALSO READ: How to Become an Artificial Intelligence Engineer

3. Database Indexing

When searching for a record in a database, the system often relies on sorted indexes like B-trees, which apply binary search principles. As a result, instead of scanning the entire dataset, binary search hones in on the desired record by eliminating half of the remaining options with every comparison. Modern relational databases, particularly in large-scale applications such as e-commerce or social media, enhance response time.

4. Parameter Tuning in Machine Learning

In Machine Learning (ML), binary search is often employed during the hyperparameter tuning process where the goal is to find the optimal parameters for a model. This tuning can involve finding the best learning rate, regularization strength, or other model parameters. The parameter space is often treated as a sorted list of potential values, and binary search can help efficiently converge on the best hyperparameter values by eliminating unsuitable values in each step. This significantly speeds up the tuning process, which is critical for training models in less time.

5. Network Routing

Network routers rely on binary search algorithms to efficiently route data through complex networks. Routers maintain tables with different IP addresses that help them decide the optimal path for data packets. Binary searches prove helpful in determining the correct path for each packet. In a high-traffic environment, routers need to make split-second decisions to minimize latency and ensure data arrives at its destination efficiently.

6. Resource Allocation and Load Balancing

Resource allocation and load balancing are crucial in AI-powered distributed systems or cloud computing environments. AI algorithms often need to allocate computational resources efficiently to handle varying workloads, and this is where the binary algorithm technique becomes useful. In essence, it helps in load-balancing algorithms by finding the optimal way to distribute tasks across servers, which is particularly important for large AI-driven applications running on distributed systems.

7. Search Engine Ranking Algorithms
After retrieving a set of pages that match a query, the search engine must quickly rank these pages based on factors like keyword density, page authority, and user engagement. To sort and retrieve the most relevant results, binary search helps rank the documents in descending order of importance. By applying binary search to the sorted list of results, search engines can deliver the most relevant pages almost instantly. This ability is why search engines like Google can return millions of results in milliseconds.

8. GPS Navigation Systems

Binary search powers GPS systems by optimizing route searches. When you input a destination, the system needs to find the best path from a massive dataset of roads, highways, and intersections. Since the road network is often sorted by distance or travel time, binary search quickly eliminates less optimal paths and directs you toward the shortest or fastest route. 

9. Decision Trees and Binary Search Logic

Decision trees, a widely used model in both AI and ML, inherently adopt a binary algorithmic approach. At each node of a decision tree, a decision splits the data into two branches based on a specific condition. Random forests and Gradient Boosting Machines (GBMs), which are advanced versions of decision trees, also rely on this kind of efficient data partitioning, drawing from binary search principles to make faster, more accurate predictions. 

10. Event Scheduling in Real-Time Systems

In real-time systems, where events must be scheduled with precise timing, binary search plays a role in managing event queues. These systems often maintain a sorted list of events organized by their scheduled execution time. When a new event is added, binary search helps place it in the correct position, maintaining the order of the queue. Additionally, binary search ensures that the system can quickly identify and execute the next event in line.

ALSO READ: I Am a Senior Engineer and This is How I Use AI Everyday

The Indian technology industry is experiencing tremendous growth. According to The Deloitte Tech Trends 2024 report,  revenue in this sector is expected to reach $254 billion in FY2024, reflecting a 3.8% year-on-year growth (1). Correlated to this are the significant advancements in AI, which is projected to grow at a 25-35% CAGR till 2027 (2). This rapid expansion is fueled by a strong AI talent base and increasing investments in AI. As the demand for skilled AI professionals continues to rise, you need to sharpen your expertise to stay ahead in this competitive landscape. 

The industry-aligned artificial intelligence courses and machine learning courses offered by Emeritus can be your go-to option for tuning your AI skills to match the AI-ready workforce of the future. These tailored programs, offered by industry leaders and globally ranked education institutes, provide cutting-edge skills that distinguish you in a fast-evolving field.

Write to us at content@emeritus.org 

Sources:

About the Author

Content Writer, Emeritus Blog
Sanmit is unraveling the mysteries of Literature and Gender Studies by day and creating digital content for startups by night. With accolades and publications that span continents, he's the reliable literary guide you want on your team. When he's not weaving words, you'll find him lost in the realms of music, cinema, and the boundless world of books.
Read More About the Author

Learn more about building skills for the future. Sign up for our latest newsletter

Get insights from expert blogs, bite-sized videos, course updates & more with the Emeritus Newsletter.

Courses on Artificial Intelligence and Machine Learning Category

IND +918068842089
IND +918068842089
article
artificial-intelligence-and-machine-learning