Skip to content

Instantly share code, notes, and snippets.

@dginev
Created April 11, 2014 23:25
Show Gist options
  • Save dginev/10509339 to your computer and use it in GitHub Desktop.
Save dginev/10509339 to your computer and use it in GitHub Desktop.
Binary Search C
#include<stdio.h>
#include<stdlib.h>
/* Just a sample binary search in C */
int binary_search(int sought_value, int* array, int array_size) {
int left,right=(0,array_size);
int middle;
while (left <= right) {
middle = (left + right) / 2;
if (array[middle] == sought_value) {
return middle; }
if (array[middle] < sought_value) {
left = middle + 1; }
else {
right = middle - 1; }
}
return -1; }
int main() {
/* We will search inside an array of even numbers */
int* even_numbers = (int *)malloc(sizeof(*even_numbers) * 10);
int even_index = 0;
for (even_index=0; even_index<10; even_index++) {
even_numbers[even_index] = 2 * even_index; }
/* And test some numbers, with both under- and overflow */
int* test_numbers = (int *)malloc(sizeof(*test_numbers) * 10);
int test_index = 0;
for (test_index=0; test_index<10; test_index++) {
test_numbers[test_index] = -2 + test_index*4; }
/* Perform actual tests: */
int search_index=0;
for (search_index=0; search_index<10; search_index++) {
printf("Search for %d returned %d\n",test_numbers[search_index],binary_search(test_numbers[search_index],even_numbers,10));
}
}
@cprodescu
Copy link

Looks good to me other than
int left,right=(0,array_size); should be
int left = 0, right = array_size - 1;

For readability, you could have statically initialized the arrays:
int even_numbers[] = {0,2,4,6,8,10,12,14,16,20};
int test_numbers[] = {-2,2,6,12,16,20,24};

and for the test,
binary_search(test_numbers[i], even_numbers, sizeof(even_numbers)/sizeof(int));

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment