title: Trouble understanding slightly modified binary search?
body: <p>Hi guys i am trying to solve a problem on leetcode called &quot;search insert position&quot;. Heres the problem:
  <a href="https://leetcode.com/problems/search-insert-position/" rel="nofollow noreferrer">https://leetcode.com/problems/search-insert-position/</a></p>
  <p>Problem statement:
  Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.</p>
  <p>You may assume no duplicates in the array.</p>
  <p>It's a simple binary search, the only part i don't understand is that i have to return the lower bound at the end to get the correct answer. I don't understand why. if anyone can explain me, i would appreciate it.</p>
  <pre><code>class Solution {
      public int searchInsert(int[] nums, int target) {
          int start=0;
          int last= nums.length-1;
          
          while(start&lt;=last){
              int middle=(start+last)/2;
              
              if(target==nums[middle]){
                  return middle;
              }
               else if(target&gt;nums[middle]){
              start=middle+1;
               }
              else
                  last=middle-1;
              
          }
          return start; // this is the part i don't understand. why do i have to return start? 
      }
  }
  </code></pre>