Skip to content

Instantly share code, notes, and snippets.

@dancarroll
Created April 23, 2010 07:21
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 dancarroll/376309 to your computer and use it in GitHub Desktop.
Save dancarroll/376309 to your computer and use it in GitHub Desktop.
Trying to write a binary search without testing
static int BinarySearch(int[] array, int target)
{
int high = array.Length - 1;
int low = 0;
int mid = (high + low) / 2;
while (high >= low)
{
if (array[mid] == target)
{
return mid;
}
else if (array[mid] > target)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
mid = (high + low) / 2;
}
return -1;
}
@dancarroll
Copy link
Author

Read this blog post: http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/

After reading, I decided to give it a try, and here's the result. Seems to work correctly. Doesn't explicitly handle the 0-length array, but handled it correctly (luckily).

@newacct
Copy link

newacct commented Apr 26, 2011

"mid" can be computed inside the loop; that way, you only need to do it once

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