How to find the number of iterations of binary search algorithm?

Question

How I can get the number of iterations of binary search?

This is my code:

int main() 
{
    int target = 11;
    int N = 10;
    std::vector<int> index;
    int num;

    for (int i = 0; i < N; i++) {
        index.push_back(i);
    }

    int counter = 0;
    unsigned int M, L = (unsigned int)-1, R = N;

    M = (R - L) / 2;  // Assume N is not zero

    do {
        int value;
        M = M + L;
        value = index[M];
        if (value < target) L = M; else R = M;
        M = (R - L) / 2;
        counter++;
    } while (M);  // M is the size of the current interval

    std::cout << R << '\n';
    std::cout << "counter: " << counter << '\n';

    system("pause");

    return 0;
}

I want to know the number of iterations depending on N. I know how this algorithm works but I want the number of iterations represented mathematically.

Rill

Since you know how the algorithm works, you know that each iteration halves the search area. You can perform successive divisions until you reach a search area of 1 with a variety of input N, plot the N versus the number of iterations and pick the curve that best fits, or you can short-circuit the curve-fitting step by already knowing which mathematical operation performs successive divisions – Mandy

Answer 1

I would go for a recursive increment of by using a recursive binary search function. In each branch of the binary checks, just increment by one and that will count the iterations recursively.

See live here

#include <iostream>
#include <vector>

std::size_t binarySearch(
    const std::vector<int>& arr,        // pass array as non-modifiyable(const ref)
    std::size_t start, std::size_t end, // start and end indexes of the array
    const int target)                   // target to find
{
    if (arr.size() == 1) return arr[0] == target ? 1 : 0; // edge case

    if (start <= end)
    {
        const std::size_t mid_index = start + ((end - start) / 2);
        return arr[mid_index] == target ? 1 :                         // found the middle element
               arr[mid_index] < target ?
                 binarySearch(arr, mid_index + 1, end, target) + 1:   // target is greater than mid-element
                 binarySearch(arr, start, mid_index - 1, target) + 1; // target is less than mid-element
    }
    return 0;
}

int main()
{
    int target = 11;
    const int N = 10;
    std::vector<int> index;
    index.reserve(N); // reserve some memory
    for (int i = 0; i < N; i++) {
        index.push_back(i);
    }
    std::cout << "counter: " << binarySearch(index, 0, index.size() - 1, target) << std::endl;
    return 0;
}

Output:

counter: 4

Lorgnon

Answer 2

Mathematically Maximum iteration possible (Assuming case of only integer type) is = ceil( log2 ( initial_r - initial_l ) ) base of log is 2 because every time we are diving our range in half by taking a mid and switching to one of the half.

Diaphaneity

Could you elaborate the idea with an example, if possible? – Tedmund

Answer 3

I have been trying to wrap my head around the logarithmic conceptualization too, and this is how I try to understand the answer

From https://en.wikipedia.org/wiki/Binary_search_algorithm

In mathematics, the binary logarithm (log₂n) is the power to which the number 2 must be raised to obtain the value n. That is, for any real number x,
x=log₂n <=equivalent to=> 2^x=n

&

Every binary tree with n leaves has height at least log₂n, with equality when n is a > power of two and the tree is a complete binary tree.

Binary search is kind of like walking down a binary search tree, and halving the nodes, and that series is a logarithmic (base 2) series _{(my own understanding, no citation, can be erroneous)}

And then from https://www.cct.lsu.edu/~sidhanti/tutorials/data_structures/page305.html

a perfect binary tree of height h has exactly 2^h+1-1 internal nodes. Conversely, the height of a perfect binary tree with n internal nodes is log₂(n+1). If we have a search tree that has the shape of a perfect binary tree, then every unsuccessful search visits exactly h+1 internal nodes, where h=log₂(n+1).

_{(again following up with my own understanding...)}
So, to reach a node N (with value N as per binary search tree?), you would make log₂(N+1) iterations (traverse that many levels down the tree) in worst case (finding is still a probability, hence "worst case" phrasing).

Dry run here (by constructing a small BST and counting manually): https://www.cs.usfca.edu/~galles/visualization/BST.html

_{(answer open for review/confirmations/corrections in phrasing/calculations too ofcourse as I am trying to consolidate different resources to reach a theory that makes sense in this context)}

Moriyama