Last active
August 29, 2015 13:56
-
-
Save cli248/9045339 to your computer and use it in GitHub Desktop.
Binary search using idea of loop invariant
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
/* | |
* 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; | |
} |
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
/* | |
* 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