Find the index position of the lower boundary in the array, then insert the data to the index, and move the index to all elements backward by one

lower_bound_and_insert_here.cpp

#include <iostream>
#include <string>

int main() {
  std::string s("ABCCDDEEFF");
  int l = 0;
  int r = s.size() - 1;
  int mid;
  char c = 'G';
  while (l <= r) {
    mid = (r - l) / 2 + l;
    if (s[mid] < c) {
      l = mid + 1;
    } else if (s[mid] == c) {
      r = mid - 1;

    } else if (s[mid] > c) {
      r = mid - 1;
    }
  }
  std::cout << s.size() << std::endl;
  s.push_back(' ');

  std::cout << s.size() << std::endl;

  for (int i = s.size() - 1; i > l; i--) {
    s[i] = s[i - 1];
  }
  s[l] = c;

  std::cout << "got insert index: " << l << std::endl;
  std::cout << "got at after insert: " << s << std::endl;
}