Skip to content

Instantly share code, notes, and snippets.

@cli248
Last active August 29, 2015 13:56
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 cli248/9045339 to your computer and use it in GitHub Desktop.
Save cli248/9045339 to your computer and use it in GitHub Desktop.
Binary search using idea of loop invariant
/*
* Given a sorted array with duplicate elements, find the first index where its element equals to target
* invariant: if key is in A[], then key's index in (low, high), and low + 1 < high
*/
int binary_search_first_position(int *A, int n, int target) {
int low = -1, high = n;
while (low + 1 < high) {
int mid = low + (high - low) / 2;
if (A[mid] < target)
low = mid;
else
high = mid;
}
if (high >= n || A[high] != target)
return -high-1;
else
return high;
}
/*
* Given a sorted array with duplicate elements, find the last index where its element equals to target
* invariant: if key is in A[], then key's index in (low, high), and low + 1 < high
*/
int binary_search_last_position(int *A, int n, int target) {
int low = -1, high = n;
while (low + 1 < high) {
int mid = low + (high - low) / 2;
if (A[mid] > target)
high = mid;
else
low = mid;
}
if (low < 0 || A[low] != target)
return -low-2;
else
return low;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment