Last active
June 11, 2017 00:53
-
-
Save jonenzl/5e995d633ef0ec7f9e6a80350ce3b5f5 to your computer and use it in GitHub Desktop.
Two searching functions - Linear search (O(n)) and binary search (O(log n))
This file contains 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
/**************************************************************************** | |
* search.c | |
* | |
* HarvardX - CS50 | |
* | |
* Two search functions. Linear search and binary search | |
***************************************************************************/ | |
/** | |
* Linear search function | |
*/ | |
bool linear_search(int value, int values[], int n) | |
{ | |
// iterate through each element of the array | |
for (int i = 0; i < n; i++) | |
{ | |
// check whether the current element is the value we are looking for | |
if (values[i] == value) | |
{ | |
return true; | |
} | |
} | |
return false; | |
} | |
//////////////////////////////////////////////////////////////////////////////////////////// | |
/** | |
* Binary search function | |
*/ | |
bool binary_search(int value, int values[], int n) | |
{ | |
// initialise variables for the limits of the search, and the middle of the array | |
int beginning = 0; | |
int ending = n - 1; | |
int middle = 0; | |
// implement binary search to look for value in array | |
// return true if value is in values[] | |
while (beginning <= ending) | |
{ | |
// set the middle of the array | |
middle = (beginning + ending) / 2; | |
// check if the middle element of the array is the value we are searching for | |
if (values[middle] == value) | |
{ | |
return true; | |
} | |
// check if the value is greater than the middle of the array | |
else if (values[middle] < value) | |
{ | |
beginning = middle + 1; | |
} | |
// check if the value is less than the middle of the array | |
else if (values[middle] > value) | |
{ | |
ending = middle - 1; | |
} | |
else | |
{ | |
break; | |
} | |
} | |
return false; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment