binary search ref: https://zxi.mytechroad.com/blog/algorithms/binary-search/sp5-binary-search/

binary_seach.java

public int binarySearch(int[] arr, int target) {
  int l = 0, r = arr.length;
  while (l < r) {
    int m = l + (r - l) / 2;
    if (arr[m] == target) return m;
    else if (arr[m] > target) {
      r = m;
    } 
    else {
      l = m + 1;
    }
  }
  return l;
}

// find(target): arr[i] = target
// lowerBound(target): 1st index i makes arr[i] >= target
// upperBound(target): 1st index i makes arr[i] > target

public int binarySearchLowerBound(int[] arr, int target) {
  int l = 0, r = arr.length;
  while (l < r) {
    int m = l + (r - l) / 2;
    else if (arr[m] >= target) {
      r = m;
    } 
    else {
      l = m + 1;
    }
  }
  return l;
}

public int binarySearchUpperBound(int[] arr, int target) {
  int l = 0, r = arr.length;
  while (l < r) {
    int m = l + (r - l) / 2;
    else if (arr[m] > target) {
      r = m;
    } 
    else {
      l = m + 1;
    }
  }
  return l;
}

// Ref
[https://zxi.mytechroad.com/blog/algorithms/binary-search/sp5-binary-search/](https://zxi.mytechroad.com/blog/algorithms/binary-search/sp5-binary-search/)