Binary Search: Traditional + Condition Based

Links To Code: 

// Binary Search - Greg Hogg DSA Course Materials Lecture 7

#include <iostream>
#include <vector>

// Traditional Binary Search - O(log n) time, O(1) space
bool binarySearch(const std::vector<int>& arr, int target) {
    int L = 0;
    int R = arr.size() - 1;

    while (L <= R) {
        int M = L + (R - L) / 2;
        if (arr[M] == target) {
            return true;
        } else if (target < arr[M]) {
            R = M - 1;
        } else {
            L = M + 1;
        }
    }
    return false;
}

// Condition-based Binary Search - O(log n) time, O(1) space
int binarySearchCondition(const std::vector<bool>& arr) {
    int L = 0;
    int R = arr.size() - 1;

    while (L < R) {
        int M = L + (R - L) / 2;
        if (arr[M]) {
            R = M;
        } else {
            L = M + 1;
        }
    }
    return L;
}

int main() {
    std::vector<int> A = {-3, -1, 0, 1, 4, 7};
    int target = 8;
    bool result = binarySearch(A, target);
    std::cout << "Is " << target << " in the array? " << (result ? "Yes" : "No") << std::endl;

    std::vector<bool> B = {false, false, false, false, false, true, true};
    int conditionResult = binarySearchCondition(B);
    std::cout << "First true element index: " << conditionResult << std::endl;

    return 0;
}
// Binary Search - Greg Hogg DSA Course Materials Lecture 7

public class Main {
    public static void main(String[] args) {
        int[] A = {-3, -1, 0, 1, 4, 7};
        int target = 8;
        boolean result = binarySearch(A, target);
        System.out.println("Is " + target + " in the array? " + result);
    }

    // Traditional Binary Search - O(log n) time, O(1) space
    public static boolean binarySearch(int[] arr, int target) {
        int L = 0;
        int R = arr.length - 1;

        while (L <= R) {
            int M = L + (R - L) / 2;
            if (arr[M] == target) {
                return true;
            } else if (target < arr[M]) {
                R = M - 1;
            } else {
                L = M + 1;
            }
        }
        return false;
    }
}


public class Main {
    public static void main(String[] args) {
        boolean[] B = {false, false, false, false, false, true, true};
        int result = binarySearchCondition(B);
        System.out.println("First true element index: " + result);
    }

    // Condition-based Binary Search - O(log n) time, O(1) space
    public static int binarySearchCondition(boolean[] arr) {
        int L = 0;
        int R = arr.length - 1;

        while (L < R) {
            int M = (L + R) / 2;
            if (arr[M]) {
                R = M;
            } else {
                L = M + 1;
            }
        }
        return L;
    }
}

Summary ▼

Binary search is an efficient algorithm used to find a target in a sorted array in O(log n) time. It works by repeatedly halving the search range based on whether the midpoint value is higher or lower than the target. Binary search can also be adapted to find boundary conditions or the first index that meets a specific criterion.

Binary Search: Traditional + Condition Based

Binary search is one of the most efficient searching algorithms available, operating in O(log n) time. It requires a sorted array and works by comparing the target value to the midpoint of the current search range.

Traditional Binary Search

The standard form of binary search is used to find the exact position of a target value. You maintain two pointers—left and right—and update them based on whether the midpoint is too high or too low.

Condition-Based Binary Search

In many problems, you're not searching for a value but rather the first or last occurrence that meets a condition. This variation is key for problems like "first true", "minimum viable value", or "find smallest/largest satisfying element".

Code Strategy

Always use mid = left + (right - left) / 2 to prevent integer overflow. Carefully choose whether the loop condition should be while (left <= right) or while (left < right) depending on the use case.

Conclusion

Binary search is a building block of many complex algorithms. By mastering both its traditional and condition-based forms, you unlock the ability to solve a wide range of problems with logarithmic efficiency.

Binary Search in Algorithms: Traditional and Condition-Based Techniques

Binary Search is one of the most fundamental and efficient search algorithms used in computer science. It is ideal for searching in sorted data structures and is widely used in algorithmic problem-solving due to its O(log N) time complexity.

1. Traditional Binary Search

The traditional binary search algorithm is used to determine whether a specific target value exists within a sorted array. This method drastically improves search performance over naive linear search by eliminating half of the remaining elements in each step.

Key Properties

  • Input Requirement: The array must be sorted in ascending order.
  • Time Complexity: O(log N)
  • Space Complexity: O(1) (iterative approach)

Implementation Steps (Iterative)

  1. Initialize:
    • Set L = 0 (start of array)
    • Set R = n - 1 (end of array)
  2. Loop While: L <= R
    • Use <= to ensure the loop includes single-element checks
  3. Calculate Middle Index:
    • M = (L + R) // 2 – Simple and common
    • M = L + (R - L) // 2 – Safer to avoid integer overflow
  4. Compare:
    • If array[M] == target → Return true
    • If array[M] > target → Search left: R = M - 1
    • If array[M] < target → Search right: L = M + 1
  5. Termination:
    • If L > R, the element is not in the array → Return false

Use Cases

  • Finding a specific number in a sorted array
  • Searching in numerical ranges or datasets
  • Validating existence of a value in ordered structures

2. Condition-Based Binary Search (Over/Under Technique)

The condition-based binary search, also called the over/under method, is used to find a boundary where a condition transitions from false to true (or vice versa). It is a powerful technique in problems involving thresholds, boundaries, or predicate-based searches.

Key Properties

  • Goal: Find the first (or last) element that satisfies a given condition
  • Requirement: The condition must partition the array into two segments — one where it is false, one where it is true
  • Time Complexity: O(log N)
  • Space Complexity: O(1)

Example Scenario

Given an array like [True, True, False, False], the task might be to find the first index where the value becomes False.

Implementation Steps

  1. Initialize:
    • L = 0
    • R = n - 1
  2. Loop While: L < R
    • Different from traditional method: this stops when L == R
  3. Calculate Midpoint: M = (L + R) // 2
  4. Evaluate Condition:
    • If condition(array[M]) == true → Move right boundary: R = M
    • If condition(array[M]) == false → Move left boundary: L = M + 1
  5. Termination:
    • When L == R, return L as the index of the boundary

Use Cases

  • Finding the first or last occurrence of a condition in a dataset
  • Solving optimization or feasibility problems (e.g., minimum capacity, maximum time)
  • Searching in [False, False, ..., True, True] or similar binary-pattern arrays

Traditional vs Condition-Based Binary Search

Feature Traditional Binary Search Condition-Based Binary Search
Use Case Find a specific target value Find boundary index satisfying a condition
Loop Condition L <= R L < R
Midpoint Adjustment R = M - 1 or L = M + 1 R = M or L = M + 1
Return Value True/False (found or not) Index of boundary
Examples Search in [1, 3, 5, 7] Search in [False, False, True, True]

Conclusion

Binary search is a versatile and powerful algorithm that extends beyond simple value lookups. Whether you're using the traditional binary search to find exact matches in sorted arrays or applying the condition-based method to identify boundaries based on predicates, mastering this O(log N) algorithm is essential for solving a wide range of problems efficiently in computer science and technical interviews.

Get Personalized Lessons at AlgoMap Bootcamp 💡