Skip to content

Instantly share code, notes, and snippets.

@joonas-yoon
Created March 28, 2020 02:08
Show Gist options
  • Save joonas-yoon/d379e8a976533024962ab02329c637eb to your computer and use it in GitHub Desktop.
Save joonas-yoon/d379e8a976533024962ab02329c637eb to your computer and use it in GitHub Desktop.
Binary search - why it can be checked by lower bound
bool binary_search(int arr[], int len, const int& key) {
int l = 0, r = len - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (arr[mid] < key)
l = mid + 1;
else
r = mid - 1;
}
return a[l] == key;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment