Skip to content

Latest commit

 

History

History
129 lines (114 loc) · 2.15 KB

README.md

File metadata and controls

129 lines (114 loc) · 2.15 KB
Raw

Binary Search Simulation

Python program to visualize the behavior of upper_bound and lower_bound binary searches.

Installation

pip install binarysearchsimulation

Overview

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