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; }

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; }

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;
}

Release files for binarysearchsimulation 1.0.2

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for binarysearchsimulation 1.0.2
File	Size	Uploaded
binarysearchsimulation-1.0.2.tar.gz	15.2 kB	May 20, 2021	Details

Built distribution (wheel)

Table of built distributions (wheels) for binarysearchsimulation 1.0.2
File	Interpreter	ABI	Platform	Reset
binarysearchsimulation-1.0.2-py3-none-any.whl 16.0 kB May 20, 2021	Python 3	none	any	Details

Total release size: 31.2 kB

Release files / binarysearchsimulation-1.0.2.tar.gz

Download URL	binarysearchsimulation-1.0.2.tar.gz
Size	15.2 kB
Tags	Source
SHA-256 checksum How to use checksums	`3869ce0f167176c3d79a330c4bd6129aab83c44e02cdfe18d76cd715994bc830`
BLAKE2b-256 checksum How to use checksums	`aa7e73eccfa4aae27901444dac8cd2a164b9157fbcff09d4de304f34aebea00f`
Upload date	May 20, 2021
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`poetry/1.0.5 CPython/3.7.4 Linux/5.10.34-1-MANJARO`

Release files / binarysearchsimulation-1.0.2-py3-none-any.whl

Download URL	binarysearchsimulation-1.0.2-py3-none-any.whl
Size	16.0 kB
Tags	Python 3
SHA-256 checksum How to use checksums	`17cec8d5ea9e27afc2300b596e25c26cbae478581ddb2222289cec4ca53d1f9c`
BLAKE2b-256 checksum How to use checksums	`32f4b6aeaf3995b97e4b806b922521d1eab8aeee50db7daebe8d3bd966230c4d`
Upload date	May 20, 2021
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`poetry/1.0.5 CPython/3.7.4 Linux/5.10.34-1-MANJARO`