Search Insert

PROBLEM

  1. In an sorted array [1, 3, 5, 6, 8], you want to know the index to insert your target, 5
  2. In an sorted array [1, 3, 5, 6, 8], you want to know the index to insert your target, 2

SOLVING

Use of Binary Search method.

  1. This code will return the index 2, where the target already is
  2. This code will return the index 1 where the target should be

Steps

  • Place Left Pointer at 0 and Right Pointer to the last element
  • Until Left Element is inferior to Right Element:
    • Get the element between left and right Middle Index=(Left Index - RIght Index) / 2
    • If Middle Element equal the target, return
    • If it’s inferior, Left Pointer becomes the Middle Pointer
    • Otherwise it’s superior, and so Right Pointer become the Middle Pointer
  • If the loop is finished return the Left Pointer

Code

#include <iostream>
#include <vector>

int searchInsert(std::vector<int> &nums, int target) {
  int l = 0;
  int r = nums.size() - 1;

  while (l <= r) {
    int m = (l + r) / 2;

    if (nums[m] == target)
      return m;
    else if (nums[m] > target)
      r = m - 1;
    else
      l = m + 1;
  }
  return l;
}

int main()
{
    // Create an empty vector
    std::vector<int> nums{1, 3, 5, 6, 8};
    std::cout << searchInsert(nums, 2) << std::endl;

    return 0;
}