algorithm-strategies.md

Algorithm Strategies

Divide and conquer

• Use two pointers as left and right bounds
• While you are in valid bounds leftBound <= rightBound
  • By using values at the bounds, indentify which half of the array your target value is in
  • Set new bounds depending on comparisons
• Return not found once the are no valid values in the domain i.e invalid bounds

Example

See Javascript

Given a sorted, rotated array like `[3, 4, 5, 1, 2]`

function findRotatedIndex(arr, k) {
  let leftBound = 0;
  let rightBound = arr.length - 1;
  let i = 0;

  while (leftBound < rightBound && ++i < 100) {
    const midIndex = Math.ceil((leftBound + rightBound) / 2);
    const midVal = arr[midIndex];

    if (midVal === k) return midIndex;

    const leftIdx = midIndex - 1;
    const rightIdx = midIndex + 1;
    let left = arr[leftIdx];
    let right = arr[rightIdx];

    if (left === k) return leftIdx;
    if (right === k) return rightIdx;
    if (k > arr[leftBound] && k < left) {
      rightBound = leftIdx;
    } else if (k < arr[rightBound] && k > right) {
      leftBound = rightIdx;
    }
  }

  return -1;
}