graphs/piscine/binary_search_ptr/bsearch.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include "bsearch.h"

#include <stddef.h>

int *binary_search(int *begin, int *end, int elt)
{
    if (begin == end)
    {
        return begin;
    }
    if (begin > end)
    {
        if (elt > *begin)
        {
            return begin + 1;
        }
        return begin;
    }

    size_t m = (end - begin) / 2;

    if (begin[m] == elt)
    {
        return begin + m;
    }

    if (begin[m] > elt)
    {
        return binary_search(begin, begin + m, elt);
    }

    if (m == 0)
    {
        m++;
    }

    return binary_search(begin + m, end, elt);
}