Skip to content

Instantly share code, notes, and snippets.

@jonenzl
Last active June 11, 2017 00:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jonenzl/5e995d633ef0ec7f9e6a80350ce3b5f5 to your computer and use it in GitHub Desktop.
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))
/****************************************************************************
* 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