Decoding Binary Search Algorithm with Examples

Decoding Binary Search Algorithm with Examples

Time Stamp: September 13, 2023 1:36 PM
Source Node: 2275926

Introduction

A Binary Search Algorithm is an efficient search technique to locate a specific object within a sorted dataset. This algorithm begins by determining the middle value of the dataset. It compares the target value with this middle value and can take one of three possible actions: 

  • If they match, the search is successful, and the index of the target value is returned.
  • If the target value exceeds the center element, the search continues with half of the dataset. 
  • If the target value is smaller, the left half is selected for further exploration

Binary search is highly efficient, boasting O(log n) time complexity, where n is the number of elements in the dataset. This makes it a preferred method for big datasets where linear search would be impractical. However, it requires that the dataset should be sorted beforehand.

Table of contents

Binary Search is an algorithm used extensively in computer science and mathematics that locates a specific element in a sorted dataset. It works by repeatedly dividing the dataset in half and comparing the target value with the middle value until the target value is discovered or determined to be absent.

What is Binary Search? 

How Binary Search Works? 

Binary search works based on three essential concepts: sorted data, divide-and-conquer, and reduction of the search area.

Sorted Data

The binary search required the dataset to be sorted in ascending or descending order. Sorting allows systematic comparison with the middle element, enabling the algorithm to determine whether or not the target value lies to the left or right.

Divide-and-Conquer

The binary search follows a divide-and-conquer policy. It starts by inspecting the middle element of the dataset and dividing it into two halves. This middle element is then compared with the target value.

  • If they match, the search is successful.
  • If the target value exceeds the middle element, the search continues with the right half of the dataset,  discarding the left half.
  • If the target value is smaller, the search continues with the left half of the dataset.

Time Complexity Analysis

  • In every step of binary search, the search space is halved. This means that only half of the dataset needs to be examined after one step.
  • With each next step, the search area is halved.
  • This method continues till the target value is discovered or the search space is reduced to an empty dataset, indicating the absence of the target element.

The time complexity of binary search may be analyzed as follows:

  • After one step, the search area is N/2, where N is the number of elements.
  • After two steps, it’s N/4.
  • After three steps, it’s N/8, and so on.

Pseudocode for Binary Search

BinarySearch(arr, target): left = 0 right = length of arr - 1 while left <= right: mid = (left + right) / 2 if arr[mid] == target: return mid // Target found, return its index else if arr[mid] < target: left = mid + 1 Else: right = mid - 1 Return -1 // Target not found.

Python Implementation

def binary_search(arr, target): left = 0 right = len(arr) - 1 while left <= right: mid = (left + right) / 2 if arr[mid] == target: return mid # Target found, return its index elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # Target not found

Handling Edge Cases and Corner Scenarios

  • Empty Array: If the input array is empty, the algorithm should return -1 as there are no elements on the search.
  • Target Not in Array: If the target value is not present in the sorted array, the algorithm returns -1.
  • Duplicate Values: Binary search works well with duplicate values. It will return the index of the first occurrence of the target value if duplicates exist.
  • Unsorted Array: Binary search assumes the input array is sorted. If the array is unsorted, the algorithm produces incorrect results. Make sure to sort the array first.
  • Integer Overflow: In some programming languages (like C++), using (left + right) / 2 for calculating the middle index might lead to integer overflow for terribly large left and right values. Using (left + (right-left)) / 2 can help prevent this.
  • Floating-Point Error: In languages that use floating-point arithmetic (like Python), using (left + right) / 2 may not be accurate for large left and right values. In such instances, using left + (right-left) /2 ensures better results.

Binary Search in Arrays

Performing a binary search on a sorted array is a common task in programming. Here are the example codes for recursive and iterative approaches to perform a binary search on a sorted array. 

Example Code: Iterative Binary Search in Python

def binary_search(arr, target):     left, right = 0, len(arr) - 1     whilst left <= right:         mid = (left + right) /2         if arr[mid] == target:             return mid  # Target found, return its index         elif arr[mid] < target:             left = mid + 1         else:             right = mid - 1     return -1  # Target not found

Example Code: Recursive Binary Search in Python

def binary_search_recursive(arr,target, left, right):     if left <= right:         mid = (left + right) / 2         if arr[mid] == target:             return mid  # Target found, return its index         elif arr[mid] < target:             return binary_search_recursive(arr, target, mid + 1, right)         else:             return binary_search_recursive(arr, target, left, mid - 1)      return -1  # Target not found

Explanation

Iterative Approach

  •  The iterative binary search starts with two pointers, left and right.
  •   It enters a “while” loop that continues till  “left” is less than or equal to “right.”
  •    Inside the loop, it calculates the “mid” index and checks whether or not the value at “mid” is equal to the target.
  •   If the target is found, it returns the index.
  •    If the target is less than the element at “mid,” it updates “right” to “mid – 1”, successfully narrowing the search to the left half of the array.
  •    If the target is greater, it updates “left” to “mid + 1”, narrowing the search to the right half.
  •   The loop continues till the target is found or “left” becomes greater than “right.” 

Recursive Approach

  •   The recursive binary search takes “left” and “right” to define the current search range. 
  •   It checks if “left” is less than or equal to “right.”
  •    It calculates the “mid” index and compares the element at “mid” with the target.
  •   If the target is found, it returns the index.
  •   If the target is less than the element at “mid,” it recursively calls itself with an updated “right” value to the left half.
  •    If the target is more, it recursively calls itself with an updated “left” value to search the right half.
  •    The recursion continues until the target is found or the search space is empty.

Binary Search in Other Data Structures 

Binary search is an effective search algorithm, but its adaptation depends on the data structure. 

BSTs (Binary Search Trees)

Binary search trees are a natural type for binary search because of their shape. It is a  tree where each node has two children, and the left subtree carries nodes with values less than the current node, while the right subtree includes nodes with values greater than the current node. Binary search can be adapted to BSTs as follows:

  • Searching in a BST: From the root node, compare the target value to the current node’s value.
  • If they match, the search is successful.
  • If the target value is less, continue the search in the left subtree.
  • If the target value is greater, continue the search in the right subtree.

Special Considerations for BSTs

  •  When adding or removing elements in a BST, it’s important to hold the BST’s properties (left < current < right for every node).
  • Balancing the tree is essential to make sure that the tree remains efficient. An unbalanced tree can degrade into linked lists, resulting in poor search times.

Use Cases

 BSTs are used in various applications, including dictionaries, databases, and symbol tables.

Arrays and Lists

Binary search can  be adapted to arrays and lists when they are sorted:

Searching in an Array or List

A binary search in an array or list is the basic example. The array or list is treated as a sequence of elements, and the algorithm proceeds.

Special Considerations

  •     The data structure should be sorted for binary search to work correctly.
  •      Ensure that you don’t get access pointers that are out of bounds.

Use Cases

Binary search in arrays or lists is used in various applications, including searching in sorted databases, finding elements in sorted collections, and optimizing algorithms like merge sort and quicksort.

Handling Duplicates 

Handling duplicates in binary search requires specific strategies to find the first, last, or all occurrences of a target value in a sorted dataset. To find the first occurrence, perform a standard binary search and return the index when the target is found. And, to find the last occurrence, modify the binary search by continuing the search in the right half when the target is found to ensure the rightmost occurrence is identified. To find all occurrences,  combine both strategies by finding the first or last occurrence and extending the search in both directions to collect all pointers. This ensures comprehensive handling of duplicates in binary search. Below are Python code examples illustrating these techniques for finding the first, last, or all occurrences:

First Occurrence

def find_first_occurrence(arr, target): left, right = 0, len(arr) - 1 result = -1 # Initialize result to -1 in case target is not found while left <= right: mid = (left + right) // 2 # Use integer division to find the midpoint if arr[mid] == target: result = mid right = mid - 1 # Continue searching in the left half for the first occurrence elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return result

Last Occurrence

def find_last_occurrence(arr, target): left, right = 0, len(arr) - 1 result = -1 # Initialize result to -1 in case target is not found while left <= right: mid = (left + right) // 2 # Use integer division to find the midpoint if arr[mid] == target: result = mid left = mid + 1 # Continue searching within the right half for the last occurrence elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return result

All Occurrences

def find_all_occurrences(arr, target): first_occurrence = find_first_occurrence(arr, target) last_occurrence = find_last_occurrence(arr, target) if first_occurrence == -1: return [] # Target not found else: return [i for i in range(first_occurrence, last_occurrence + 1)]

Binary Search Variation

  • Ternary Search divides the search space into three elements by evaluating the target with elements at two equally spaced midpoints. This can be more efficient when dealing with functions with a single maximum or minimum, reducing the number of comparisons.
  • Exponential Search is beneficial for unbounded lists. It starts with small steps and exponentially increases the range until a boundary is found, then applies binary search within that range.

Binary Search Optimization

Optimizing binary search algorithms involves improving their overall growth and performance. Strategies include Jump Search, which combines linear and binary searches by jumping in advance in fixed steps, reducing comparisons for huge arrays. Interpolation Search is another method that estimates the target’s position primarily based on the data distribution, leading to faster convergence, specifically for uniformly distributed data.

Benchmarking and profiling are vital for optimizing binary search on large datasets. Profiling tools identify bottlenecks, helping to fine-tune the code. Benchmarks compare the algorithm’s execution time under different situations, guiding optimizations. These techniques ensure binary search performs optimally in diverse situations, from databases to game development, where efficiency and speed are important.

  • Not Checking for Sorted Data: Not ensuring the data is sorted before a binary search can lead to incorrect results. Always verify data is sorted first.
  • Incorrect Midpoint Calculation: Using (left + right) / 2 for midpoint calculation may additionally cause integer overflow or precision problems in some languages. Use (left + (right-left)) / 2 to avoid these issues.
  • Infinite Loops: Failing to replace pointers (left and right) correctly in the loop can result in infinite loops. Ensure they’re updated regularly.

Real-World Applications

Binary search is ubiquitous in computer science and beyond. It’s used in search engines like Google and Yahoo for instant retrieval of web pages, databases for efficient querying, and file systems for fast data retrieval. Airlines use it to optimize seat booking, and it plays a pivotal role in data compression algorithms. 

Binary Search Libraries and Modules 

Many popular programming languages offer in-built libraries or modules that offer efficient binary search implementations. In Python, the “bisect” module provides functions like “bisect_left,” “bisect_right,” and “bisect” for searching and inserting elements into sorted lists.

These library functions are optimized for performance and can save time and effort in coding custom binary search algorithms.

Conclusion 

Binary search is a flexible and efficient algorithm for quickly finding elements in sorted data structures. It offers a foundation for optimizing diverse applications, from search engines like Google and Yahoo to game development. By understanding its principles and considering variations and libraries, builders can utilize the strength of binary search to solve complex problems successfully and expediently.

If you are interested in knowing more about such algorithms, then our free courses and blogs can help you a lot.

Frequently Asked Questions

Q1. What is the key advantage of binary search over linear search? 

A. Binary search offers faster search instances with a time complexity of O(log n) compared to linear search’s  O(n) for large datasets.

Q2. When should I choose ternary search over binary search?

A. Ternary search is preferred while searching to find a single maximum or minimum in an unimodal function, providing faster convergence.

Q3. How can I handle duplicates efficiently in binary search?

A. To handle duplicates, you can modify binary search to find the first, last, or all occurrences of a target value, depending on your requirements.

Time Stamp:

More from Analytics Vidhya