3
\$\begingroup\$

I wrote a non recursive binary search implementation in C, for this time I think there are no bugs.

Here's the code:

size_t search_no_recursion(int *arr, int target, int start, int end) {
        size_t middle;

        while(start < end) {
                middle = (start + end) / 2;

                if(target == arr[middle])
                        return middle;
                else if(target < arr[middle])
                        end = middle;
                else {
                        start = middle;
                        ++start;
                        /*
                           if `start` isn't incremented and the input is bigger
                           than the last element, the while loop will go forever
                           because `start` will never be bigger than `end`
                         */
                }
        }

        return -1;
}

What do you think about this code? Is it good or bad?
And I'm sorry if this is a very dumb question.

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

There is a bug here: if the final partition of the array gives a one-element slice, and it was either the initial slice or above the previous middle, the algorithm fails to find the element, because it checks that the size of the slice is greater than 1 before it checks whether its one element is a solution. You can reproduce this on any singleton array, for example:

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
    
int main(void) {
  const int array[] = {1};
    
  const ptrdiff_t result = search_no_recursion( array, 1, 0, sizeof(array)/sizeof(array[0])-1);
    
  printf("%td\n", result);

  return EXIT_SUCCESS;
}

This will also show that you return -1, but implicitly cast that to size_t, meaning it becomes the valid positive quantity 0xffffffffUL or 0xffffffffffffffffULL. Your unsigned result is valid if it is less than -1. You probably want to declare your error value as SIZE_MAX from <stdint.h>, or perhaps change the return type to the signed type ptrdiff_t, which would allow -1 to behave as expected but gives you a range of 63 bits on 64-bit systems, rather than 31. But definitely name it, and define it so it doesn’t have the issues with implicit type conversion that might cause you to end up mixing up 0xffffffff and 0xffffffffffffffff on a 64-bit system. This will also make the code more readable.

A smaller bug here is that, on a large array, start + end could overflow, which is undefined behavior for a signed value. On most modern architectures, int is a signed 32-bit quantity, so you’re limiting the range of this function to only a little more than a billion elements before the sum of the endpoints would exceed INT_MAX.

Not a bug in the code shown here, per se, but a problem with what you don’t say, is that you never say that this has to be called with end set to the index of the last valid element of the array, not one past the end of the array. It is very easy to call this API with a fencepost error, which will cause a buffer overrun.

The middle variable is never accessed outside the loop, or by any future iteration of the loop before it is updated, so you could make it a static single assignment inside the scope of the loop. This gets the compiler to prevent a wide range of bugs, and can also help the optimizer out sometimes. (For example, I’ve gotten more-optimized code because the compiler can tell that a variable I declared within a loop cannot be aliased by any pointer in scope, which it could not do for a mutable variable declared outside the loop.)

So one improvement would be to declare const size_t middle = start/2 + last/2 inside the loop, and leave everything else the same. (As @mdfst brings up, an alternative is (last-start)/2 + start, which is a closer equivalent because it yields the same result as (last+start)/2 for all valid inputs.)

You normally want your indices to be type size_t, not int. If you want to use signed values, the type you want is probably ptrdiff_t so that you can access array elements above 2 giga. It’s bad practice to compare signed and unsigned quantities as you do here. This can give you some very surprising bugs using C’s implicit scalar promotions, such as middle being smaller than -1 because the literal -1 gets promoted to the unsigned value INT_MAX). If your compiler isn’t warning you about this, you should enable more warnings. On gcc/clang/icx, I normally use -Wall -Wextra -Wpedantic -Wconversion -Wdeprecated, along with -std=. This one should be enabled by -Wconversion.

The arr argument is not declared const, even though its elements are only read and never modified. C lets you get away with this, but it’s bad practice to give a function permission to modify an array, when it is meant to accept constant data.

On a minor note, you could save a line of code with start = middle + 1;.

To use size_t, #include <stddef.h>.

Finally, converting recursive algorithms to iterative loops is a useful skill, but be aware that a tail-recursive function will give you code that’s just as efficient as the loop. Comparing on Godbolt, Clang 15.0.0 with -Os -std=c17 -march=x86-64-v4 compiles your code to:

search_no_recursion:                    # @search_no_recursion
        cmp     edx, ecx
        jge     .LBB0_5
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        lea     eax, [rcx + rdx]
        mov     r8d, eax
        shr     r8d, 31
        add     r8d, eax
        sar     r8d
        movsxd  rax, r8d
        mov     r9d, dword ptr [rdi + 4*rax]
        cmp     r9d, esi
        je      .LBB0_6
        jg      .LBB0_4
        inc     r8d
        mov     edx, r8d
        mov     r8d, ecx
.LBB0_4:                                #   in Loop: Header=BB0_1 Depth=1
        mov     ecx, r8d
        cmp     edx, r8d
        jl      .LBB0_1
.LBB0_5:
        mov     rax, -1
.LBB0_6:
        ret

which is not bad at all; the main loop is 16 instructions long. Let’s compare a tail-recursive version:

#define NOT_FOUND SIZE_MAX

size_t search_tail_recursion( const int array[],
                              const int target,
                              const size_t start,
                              const size_t end )
{
  const size_t middle = (end-start)/2 + start;
  const int pivot = array[middle];

  return (pivot == target) ? middle :
         (start >= end)    ? NOT_FOUND :
         (pivot > target)  ? search_tail_recursion( array, target, start, middle ) :
                             search_tail_recursion( array, target, middle+1, end );
}

I personally like this quasi-functional style: the compiler checks that every variable in the local state will be updated once, and only once, before it is used. It also happens to be shorter. This code also fixes the bugs mentioned above. What code does it generate? Under the same flags,

search_tail_recursion:                  # @search_tail_recursion
.LBB1_1:                                # =>This Loop Header: Depth=1
        mov     rax, rcx
.LBB1_2:                                #   Parent Loop BB1_1 Depth=1
        sub     rax, rdx
        shr     rax
        add     rax, rdx
        mov     r8d, dword ptr [rdi + 4*rax]
        cmp     r8d, esi
        je      .LBB1_5
        cmp     rcx, rdx
        jbe     .LBB1_4
        cmp     r8d, esi
        jle     .LBB1_8
        mov     rcx, rax
        jmp     .LBB1_2
.LBB1_8:                                #   in Loop: Header=BB1_1 Depth=1
        inc     rax
        mov     rdx, rax
        jmp     .LBB1_1
.LBB1_4:
        mov     rax, -1
.LBB1_5:
        ret

Very similar, but it turns out that the compiler recognizes this algorithm and optimizes it slightly better than the other variations I tried. So, if you can make your recursive function tail-recursive, that’s usually equivalent to a while loop, as it is here. You might still want a while loop for various reasons, but it’s not any more efficient on a modern optimizing compiler.

\$\endgroup\$
0
1
\$\begingroup\$

The function signature doesn't make sense to me:

size_t search_no_recursion(int *arr, int target, int start, int end)

If we return the position as a size_t, then shouldn't start and end also be size_t?

The other thing that's missing is a specification. I have to assume from experience that start is inclusive and end exclusive, but it would be nice to see that confirmed. Here, in review, I can just look at the code and see it returns (size_t)-1 when the target isn't found, for example, but that gets harder and harder as function size increases. Get into the habit of making it clearer what behaviour is expected.


Passing start is unnecessary, because callers can always create a subrange in C by adding start to arr and subtracting it from end (and, of course, adding it to the result).


An alternative behaviour when the target isn't found is to return the position where it should be inserted (e.g. 0 if target < arr[0], or end if target >= arr[end-1]. Callers can then determine whether the target was found (if result < end && arr[result] == target). Alternatively, return a boolean value, and pass a pointer to write the result to (e.g. bool search(int *array, size_t length, int target, size_t& position)). Either way, this allows a single function to be used both for insertion and for lookup.


If you really want to please reviewers, then include some unit tests that show all the edge-cases that you have proven to work.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.