title: Binary search for the closest value less than or equal to the search value
body: <p>I'm trying to write an algorithm for finding the index of the closest value that is lesser than or equal to the search value in a sorted array. In the example of the array <strong>[10, 20, 30]</strong>, the following search values should output these indexes:</p>
  
  <ol>
  <li>searchValue: 9, index: -1</li>
  <li>searchValue: 10, index: 0</li>
  <li>searchValue: 28, index: 1</li>
  <li>searchValue: 55555, index: 2</li>
  </ol>
  
  <p>I want to use binary search for logarithmic runtime. I have an algorithm in C-esque psuedocode, but it has 3 base cases. Can these 3 base cases be condensed into 1 for a more elegant solution?</p>
  
  <pre><code>int function indexOfClosestLesser(array, searchValue, startIndex, endIndex) {
    if (startIndex == endIndex) {
      if (searchValue &gt;= array[startIndex]) {
        return startIndex;
      } else {
        return -1;
      }
    }
  
    // In the simplistic case of searching for 2 in [0, 2], the midIndex
    // is always 0 due to int truncation. These checks are to avoid recursing
    // infinitely from index 0 to index 1. 
    if (startIndex == endIndex - 1) {
      if (searchValue &gt;= array[endIndex]) {
        return endIndex;
      } else if (searchValue &gt;= array[startIndex]) {
        return startIndex;
      } else {
        return -1;
      }
    }
  
    // In normal binary search, this would be the only base case
    if (startIndex &lt; endIndex) {
      return -1;
    }
  
    int midIndex = endIndex / 2 + startIndex / 2;
    int midValue = array[midIndex];
  
    if (midValue &gt; searchValue) {
      return indexOfClosestLesser(array, searchValue, startIndex, midIndex - 1);
    } else if (searchValue &gt;= midValue) {
      // Unlike normal binary search, we don't start on midIndex + 1.
      // We're not sure whether the midValue can be excluded yet
      return indexOfClosestLesser(array, searchValue, midIndex, endIndex);
    }
  }
  </code></pre>