Binary Search

1. Search Mechanism

Calculate the middle index, compare it with the target, and narrow down the search to either the left or right half.

2. Efficiency

More efficient in practice due to fewer comparisons. It effectively halves the search space with each iteration.

3. Implementation Complexity

Easier to implement with less code and straightforward logic.
Commonly used in programming languages and libraries.

4. Use Cases

Used in various applications, including searching in databases, data structures, and algorithms where sorted data is involved.

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = intval(($left + $right) / 2);
        
        if ($arr[$mid] == $target) {
            return $mid; // Target found
        }
        
        if ($arr[$mid] < $target) {
            $left = $mid + 1; // Search right half
        } else {
            $right = $mid - 1; // Search left half
        }
    }
    
    return -1; // Target not found
}

// Example usage
$numbers = [1, 3, 5, 7, 9, 11];
$target = 7;
$result = binarySearch($numbers, $target);
echo "Binary Search Result: " . ($result != -1 ? "Found at index $result" : "Not found") . "\n";

Ternary Search

1. Search Mechanism

Divide the array into three parts by calculating two midpoints. Compare the target with the values at these midpoints to determine which segment to search next (left, middle, or right).

2. Efficiency

Although it reduces the search space, it performs more comparisons than binary search. It effectively divides the search space into thirds, making it less efficient in practice for large datasets.

3. Implementation Complexity

More complex to implement than binary search due to the need for calculating two midpoints and handling three segments. This can lead to increased code complexity and potential for errors.

4. Use Cases

Primarily used for optimization problems involving unimodal functions, where you need to find the maximum or minimum value. Not commonly used for standard search tasks in sorted arrays.

function ternarySearch($arr, $left, $right, $target) {
    if ($right >= $left) {
        $mid1 = intval($left + ($right - $left) / 3);
        $mid2 = intval($right - ($right - $left) / 3);

        if ($arr[$mid1] == $target) {
            return $mid1; // Target found
        }
        if ($arr[$mid2] == $target) {
            return $mid2; // Target found
        }

        if ($target < $arr[$mid1]) {
            return ternarySearch($arr, $left, $mid1 - 1, $target); // Search in the left third
        } elseif ($target > $arr[$mid2]) {
            return ternarySearch($arr, $mid2 + 1, $right, $target); // Search in the right third
        } else {
            return ternarySearch($arr, $mid1 + 1, $mid2 - 1, $target); // Search in the middle third
        }
    }
    return -1; // Target not found
}

// Example usage
$numbers = [1, 3, 5, 7, 9, 11];
$target = 7;
$result = ternarySearch($numbers, 0, count($numbers) - 1, $target);
echo "Ternary Search Result: " . ($result != -1 ? "Found at index $result" : "Not found") . "\n";

Newest Articles & Insights

Impact of HIPAA on Software Development: Design and Compliance Best Practices

Impact of HIPAA on Software Development: Design and Compliance Best Practices

Why Binary Search is Preferred Over Ternary Search?

Why Binary Search is Preferred Over Ternary Search?

Understanding the N+1 Problem in Django and How to Fix It

Understanding the N+1 Problem in Django and How to Fix It