title: Binary search to insert a value to a sorted list
body: <p>I'm trying to insert values from list B in to list A. </p>
  
  <p>List A is always sorted in descending order and can get quite big (2x10^5).</p>
  
  <p>List B is always sorted in ascending order and can also be of the size 2x10^5</p>
  
  <p>I want to insert the values from B to A whilst still having the descending order. I used binary search to find the index positions of where I should add the value.</p>
  
  <p>However for this one test case I am having a peculiar bug that I can't seem to fix </p>
  
  <pre><code>def binarySearch(arr, low, high, x):
      while low &lt; high:
          mid = low + (high - low) // 2;
          if arr[mid] == x:
              return mid
          elif arr[mid] &lt; x:
              high = mid - 1
          else:
              low = mid + 1
      if low &gt;= high:
          return(low)
  
  for i in B:
      indexpos = binarySearch(A, 0, len(A)-1, i)
      if indexpos == 0:
          A = [i] + A
      else:
          A = A[:indexpos+1] + [i] + A[indexpos+1:]
      print(A)
  </code></pre>
  
  <p>Here is a sample input that works:</p>
  
  <pre><code>A = [100,100,50,40,40,20,10]
  B = [5,25,50,120]
  
  Output: A = [120, 100, 100, 50, 50, 40, 40, 25, 20, 10, 5]
  </code></pre>
  
  <p>I can't figure out why this one doesn't work:</p>
  
  <pre><code>A = [100,90,90,80,75,60]
  B = [50,65,77,90,102]
  
  Output: A = [102, 100, 90, 90, 90, 80, 75, 77, 65, 60, 50]
  </code></pre>
  
  <p>Any help would be much appreciated</p>