Search Insert Position in a sorted array. Find the index of a value in a sorted array or return the index where it should be placed. Searches array using divide and conquer.

searchInsert.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    var start = 0;
    var end = nums.length - 1;
    var index = Math.floor((end - start) / 2) + start;
    
    if (target > nums[nums.length-1]) {
        // The target is beyond the end of this array.
        index = nums.length;
    }
    else {
        // Start in middle, divide and conquer.
        while (start < end) {
            // Get value at current index.
            var value = nums[index];
            
            if (value === target) {
                // Found our target.
                result = index;
                break;
            }
            else if (target < value) {
                // Target is lower in array, move the index halfway down.
                end = index;
            }
            else {
                // Target is higher in array, move the index halfway up.
                start = index + 1;
            }
            
            // Get next mid-point.
            index = Math.floor((end - start) / 2) + start;
        }
    }
    
    return index;
};

zexample.txt

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.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

No need for result = index;

A more generic version using compare function

For reference:

// Finds the insertion index for an item in an array.
// Uses compareFn (similar to that provided to array.sort())
const getInsertionIndex = (arr, item, compareFn) => {
  const itemsCount = arr.length;

  // No items in array, so return insertion index 0
  if (itemsCount === 0) {
    return 0;
  }

  const lastItem = arr[itemsCount - 1];

  // In case the item is beyond the end of this array, or
  // identical to the last item.
  // We need this as for arrays with 1 item start and end will be
  // 0 so we never enter the while loop below.
  if (compareFn(item, lastItem) >= 0) {
    return itemsCount;
  }

  const getMidPoint = (start, end) => Math.floor((end - start) / 2) + start;
  let start = 0;
  let end = itemsCount - 1;
  let index = getMidPoint(start, end);;

  // Binary search - start in middle, divide and conquer.
  while (start < end) {
    const curItem = arr[index];

    const comparison = compareFn(item, curItem);

    if (comparison === 0) {
      // Indentical item
      break;
    } else if (comparison < 0) {
      // Target is lower in array, move the index halfway down.
      end = index;
    } else {
      // Target is higher in array, move the index halfway up.
      start = index + 1;
    }
    index = getMidPoint(start, end);
  }

  return index;
};