title: Is it possible to insert a number into a sorted array, time: log(n)
body: <p>I have a sorted array of integers (of size n) and would like to insert a new element into the array, is it possible to do so in O(log(n))? I need to keep an insertion and find computational complexity of O(log(n))).</p>
  <p>Right now the only idea I have is to do binary search in order to find the desired index for insertion - this would take O(log(n)), but then I would have to create a new array and copy the entire cells which would take O(n).</p>
  <p>EDIT:<br />
  It was solved by using an <a href="https://en.wikipedia.org/wiki/AVL_tree" rel="nofollow noreferrer">AVL Tree</a> instead, that way any new elements added takes O(log(n)) and finding an element takes O(log(n))</p>