binary_search.h File Reference

Binary search on sorted arrays. O(log n) time, O(1) space. More...

#include <stddef.h>

Go to the source code of this file.

Macros
#define	BSEARCH_NOT_FOUND   ((size_t)-1)

Functions
size_t	binary_search_ints (const int *arr, size_t n, int target)
size_t	binary_search_ints_recursive (const int *arr, size_t lo, size_t hi, int target)
size_t	binary_search_strings (const char *const *arr, size_t n, const char *target)

Detailed Description

Binary search on sorted arrays. O(log n) time, O(1) space.

Returns the index of the target if found, or (size_t)-1 if not. The input array MUST be sorted in ascending order — the caller's responsibility, not checked here.

Definition in file binary_search.h.

Macro Definition Documentation

BSEARCH_NOT_FOUND

#define BSEARCH_NOT_FOUND   ((size_t)-1)

Definition at line 15 of file binary_search.h.

Function Documentation

binary_search_ints()

size_t binary_search_ints	(	const int *	arr,
		size_t	n,
		int	target
	)

Definition at line 13 of file binary_search.c.

References BSEARCH_NOT_FOUND.

Referenced by main().

binary_search_ints_recursive()

size_t binary_search_ints_recursive	(	const int *	arr,
		size_t	lo,
		size_t	hi,
		int	target
	)

Definition at line 46 of file binary_search.c.

References binary_search_ints_recursive(), and BSEARCH_NOT_FOUND.

Referenced by binary_search_ints_recursive().

binary_search_strings()

size_t binary_search_strings	(	const char *const *	arr,
		size_t	n,
		const char *	target
	)

Definition at line 29 of file binary_search.c.

References BSEARCH_NOT_FOUND.