Python program to visualize the behavior of upper_bound and lower_bound binary searches.
Project description
Binary Search Simulation
Python program to visualize the behavior of upper_bound and lower_bound binary searches.
Upper Bound | Lower Bound |
---|---|
Intuitive Binary Search | |
---|---|
Upper Bound | Lower Bound |
int upperBound(vector<int> &array, int target) {
// array should be sorted in non-decreasing
// order from left to right
int l = 0, r = array.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (target < array[mid]) {
r = m - 1;
} else {
l = m + 1;
}
}
return l;
}
|
int lowerBound(vector<int> &array, int target) {
// array should be sorted in non-decreasing
// order from left to right
int l = 0, r = array.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (target <= array[mid]) {
r = m - 1;
} else {
l = m + 1;
}
}
return l;
}
|
Binary Search Variation (works optimally for non-integer spaces) | |
---|---|
Upper Bound | Lower Bound |
int upperBound(vector<int> &array, int target) {
// array should be sorted in non-decreasing
// order from left to right
int l = -1, r = array.size();
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (target < array[mid]) {
r = m;
} else {
l = m;
}
}
return r;
}
|
int lowerBound(vector<int> &array, int target) {
// array should be sorted in non-decreasing
// order from left to right
int l = -1, r = array.size();
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (target <= array[mid]) {
r = m;
} else {
l = m;
}
}
return r;
}
|
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Close
Hashes for binarysearchsimulation-1.0.1.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 40f04c6df16a1e628065fce3bef52d0f219a6970c8df84964144b0202e9d167f |
|
MD5 | 175a5df9e5c9184a2720ba972114bbe4 |
|
BLAKE2b-256 | 1ec3696b41262947aaa6af866ad1e8eee2bc29a7fe46b8c2273620136468769d |
Close
Hashes for binarysearchsimulation-1.0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a0aebb0adbfd5568366c61587c9a988e8cfb22a27d73a0f2d49101cc8db54b7a |
|
MD5 | c68265bfeba87364c2fc24038966799a |
|
BLAKE2b-256 | 98c1155fc06b45a4a60297bf17cf36e42a4ad46e0272983b07f0cfe9fff7e7f3 |