Created
April 23, 2010 07:21
-
-
Save dancarroll/376309 to your computer and use it in GitHub Desktop.
Trying to write a binary search without testing
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
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; | |
} |
"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
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).