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.
