Created
April 11, 2014 23:25
-
-
Save dginev/10509339 to your computer and use it in GitHub Desktop.
Binary Search C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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));