Sujith's Library

Appearance

Binary Search ​

Page 177

The Binary Search algorithm is a highly efficient method for searching for a specific key within a sorted array.

It is a prime example of a decrease-by-a-constant-factor algorithm because it repeatedly divides the search space in half during each iteration.

  1. It compares the search key K with the middle element A[m] of the array.
  2. If K matches A[m], the search is successful, and the algorithm stops.
  3. If they do not match, the algorithm recursively continues the search in either the first half of the array (if K < A[m]) or the second half of the array (if K > A[m]).

Prerequisites and Limitations ​

  • Sorted Array: Input array must be sorted in ascending order is the fundamental prerequisite for Binary Search.

  • Random Access: Its efficiency relies on the ability to access any element of the array in constant time (random access). Therefore, it is not suitable for searching in linked lists, as reaching the middle element in a linked list takes Θ(n) time, making Binary Search inefficient for such data structures.

Algorithms like interpolation search and hashing can achieve better average-case time efficiency, though they may require additional special calculations or do not require the array to be sorted, respectively.

ALGORITHM BinarySearch(A[0..n − 1], K)
// Implements nonrecursive binary search
// Input: An array A[0..n − 1] sorted in ascending order and a search key K
// Output: An index of the array’s element that is equal to K
//         or −1 if there is no such element

l <- 0        // Initialize left pointer to the first index
r <- n − 1    // Initialize right pointer to the last index

while l ≤ r do
    m <- ⌊(l + r) / 2⌋ // Calculate the middle index

    if K = A[m] then
        return m             // Key found at index m
    else if K < A[m] then
        r <- m − 1          // Search in the left half
    else          
        l <- m + 1          // Search in the right half
        
return −1

Searches for a given value K in a sorted subarray A[l..r] using recursion.

Algorithm RecursiveBinarySearch(A, l, r, K):
// A: sorted array
// l: left index
// r: right index
// K: search key

if l > r then
	return -1   // Base case: subarray empty, key not found

m <- floor((l + r) / 2)   // Middle index

if K == A[m] then
	return m             // Key found
else if K < A[m] then
	return RecursiveBinarySearch(A, l, m - 1, K)
else
	return RecursiveBinarySearch(A, m + 1, r, K)
  • Works only on sorted arrays.
  • Time Complexity: O(log n) in best/average case; O(n) if recursion is misused on unsorted data.
  • Space Complexity: O(log n) due to recursive calls.

Proof of Worst-Case Time Complexity ​

To prove the worst-case time complexity, we analyze the number of key comparisons the algorithm makes.

  • Basic Operation: The basic operation is the comparison of the search key with an element of the array. For simplicity, we count "three-way comparisons" (less than, equal to, or greater than).

  • Recurrence Relation: In the worst case, Binary Search continuously reduces the size of the array by about half at each step, and the key is either not found or found at the very last step.

    • Let C(n) be the number of key comparisons in the worst case for an array of size n.
    • If n > 1, one comparison is made (with A[m]), and the problem is reduced to searching in a subarray of size ⌊n/2⌋ (or ⌈n/2⌉ depending on the exact implementation and which half is taken).
    • The recurrence relation is therefore: C(n) = C(⌊n/2⌋) + 1 for n > 1.
    • Initial Condition: For an array of size 1, C(1) = 1 comparison is needed.

  • Solving the Recurrence: To solve C(n) = C(⌊n/2⌋) + 1 with C(1) = 1, let's consider n as a power of 2, i.e., n = 2^k for some integer k ≥ 0.

    • C(2^k) = C(2^(k-1)) + 1
    • Substituting recursively:
    • C(2^k) = (C(2^(k-2)) + 1) + 1 = C(2^(k-2)) + 2
    • C(2^k) = (C(2^(k-3)) + 1) + 2 = C(2^(k-3)) + 3
    • ... C(2^k) = C(2^(k-k)) + k = C(1) + k
    • Given C(1) = 1, we have C(2^k) = 1 + k.
    • Since n = 2^k, then k = log₂n.
    • Therefore, C(n) = log₂n + 1.

The worst-case of comparisons is given by: Cworst(n) = ⌈log₂n⌉ + 1.

Indicates that the worst-case time efficiency of Binary Search is in Θ(log n), which is very efficient because the logarithmic function grows very slowly.

This logarithmic growth means that even for very large arrays, the number of comparisons remains small. For instance, it takes at most 10 comparisons for an array of 1,000 elements and no more than 20 comparisons for an array of 1,000,000 elements.

Principles of Parallel Algorithm Design ​

When designing parallel algorithms, the core concept is to break down a large problem into smaller pieces that can be executed concurrently by different processors. This process is called decomposition, and the way it's done is fundamental to the algorithm's performance.

The smallest units of work resulting from decomposition are called tasks. These are programmer-defined, indivisible units of computation that can be run in parallel.

Main Decomposition Strategies ​

The two primary strategies for breaking down a problem are Task Decomposition and Data Decomposition.

The key difference lies in what you focus on splitting: the work to be done or the data to be processed.

Task Decomposition (Task Parallelism) ​

Task decomposition focuses on identifying independent computations that can be executed concurrently. The algorithm is broken down into a collection of distinct, often different, functions or processes.

The focus is computational work, looking for different operations that can run in parallel.

Data Decomposition (Data Parallelism) ​

Data decomposition focuses on distributing the data the algorithm operates on across different processors. Each processor then typically performs the same operation on its assigned chunk of data.

The operations are usually identical, but they act on different pieces of the data. The computational tasks are implicitly created by this data partitioning.

Specific Decomposition Techniques ​

These common patterns are used to implement the strategies above.

1. Data Partitioning ​

This technique is a direct application of data decomposition and is ideal for problems with large datasets. The core idea is to first partition the data and then assign computations based on that partition, often using an "owner-computes" rule (where the processor that "owns" a piece of data is responsible for computing on it).

  • Examples: if you have a large array to process, you could divide the array into smaller chunks (data partitioning), and then assign different processors to compute on their respective chunks (computational partitioning).

2. Recursive Decomposition ​

This technique, a form of task decomposition, is perfect for problems that can be solved using a divide-and-conquer approach. A problem is recursively broken down into smaller, independent subproblems of the same type. These subproblems can be solved in parallel, and their results are combined for the final solution.

  • Quicksort/Mergesort: An array is repeatedly split into halves, which are then sorted concurrently and recursively.

  • Finding the Sum of n Numbers: Instead of a sequential sum, the list is split into two halves. Their sums are computed in parallel, and the two results are added. With enough processors, this can reduce the time from O(n) to O(log2​n).

  • Strassen’s Matrix Multiplication and many binary tree traversals also use this method.

3. Exploratory Decomposition ​

This is a form of task decomposition used for problems that involve searching a large space of solutions, often visualized as a tree. The decomposition involves assigning different processors to explore different branches of the search tree in parallel.

When one task finds a solution, other tasks exploring different branches can often be terminated.

  • Backtracking Algorithms: Used in problems like the n-Queens problem or finding a Hamiltonian Circuit, where different paths in the state-space tree are explored simultaneously.

  • Branch-and-Bound Algorithms: Used in optimization problems like the Traveling Salesperson Problem (TSP), where different processors explore potential solutions while pruning branches that cannot lead to an optimal result.

4. Speculative Decomposition ​

This technique is used when the flow of computation is uncertain, depending on the result of a previous task. It involves "speculating" or guessing an outcome and proactively executing subsequent tasks based on that guess.

If the prediction is correct, time is saved. If it's wrong, the speculative work is discarded, which can incur overhead to restore the previous state. However, for some problems, this is the only way to achieve parallelism.

  • Example: Discrete Event Simulation. In a simulation, multiple possible future event paths can be computed concurrently. Once the actual event outcome is determined, the results from the incorrect speculative paths are thrown away.

Key Concepts in Parallel Design ​

Task Dependency and Interaction Graphs ​

In most parallel computations, there are dependencies between different tasks, meaning certain tasks can only begin once other tasks have finished, tasks are not entirely independent. These dependencies are explicitly represented using a directed acyclic graph (DAG).

  • Task-Dependency Graph: A directed acyclic graph (DAG) where nodes represent tasks and edges represent dependencies. A task can only be executed after all tasks with incoming edges to it are complete. This graph defines the essential ordering constraints.

    • Example: A "producer" task generates data that a "consumer" task needs. The consumer task depends on the producer.

  • Task-Interaction Graph: This graph shows all interactions (e.g., communication or shared data access) between tasks. It is a superset of the dependency graph, as tasks can interact without being strictly dependent.

Granularity ​

Granularity refers to the number and size of tasks a problem is broken into.

  • Fine-grained decomposition: Many small tasks. This increases the potential for parallelism but can also increase overhead from communication and scheduling.

  • Coarse-grained decomposition: Few large tasks. This has lower overhead but may limit the amount of parallelism available.

Degree of Concurrency ​

This metric indicates how many tasks can be executed in parallel at any point in the algorithm. The average degree of concurrency is a useful measure of an algorithm's overall parallelism. Generally, a finer granularity leads to a higher degree of concurrency.

Critical Path Length ​

The critical path is the longest path (in terms of execution time) through the task-dependency graph. Its length determines the absolute minimum execution time for the entire computation, even with infinite processors.

Because all tasks on this path have sequential dependencies. No matter how many tasks are executed in parallel, the total time will always be at least as long as the critical path, as tasks along this path must be executed sequentially due to their dependencies.

Made with ❤️ for students, by a fellow learner.

© 2025 Sujith.