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.2.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3869ce0f167176c3d79a330c4bd6129aab83c44e02cdfe18d76cd715994bc830 |
|
MD5 | 7fbca3d809abc5d1ebcb25e39a0a9201 |
|
BLAKE2b-256 | aa7e73eccfa4aae27901444dac8cd2a164b9157fbcff09d4de304f34aebea00f |
Close
Hashes for binarysearchsimulation-1.0.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 17cec8d5ea9e27afc2300b596e25c26cbae478581ddb2222289cec4ca53d1f9c |
|
MD5 | 1b958a536c1ed55e0fbb8786ac382acc |
|
BLAKE2b-256 | 32f4b6aeaf3995b97e4b806b922521d1eab8aeee50db7daebe8d3bd966230c4d |