Binary Search Hacks

Homework Hacks

Homework Hack 1: Binary Search on a Rotated Array

Description: You are given a sorted array that has been rotated at some unknown pivot. Write a function that uses Binary Search to find a target element in this rotated array. If the element is found, return its index. If not, return -1.

%%html
<script>
    let arr = [4, 5, 6, 7, 0, 1, 2]
    let target = 1
    console.log("Our array is:" + arr + ", and our target is:" + target)

    arr.sort()

function binarySearch(array, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1; // search right 
    } else {
      right = mid - 1; // search left 
    }
  }

  return -1;
}

console.log(binarySearch (arr, target))

</script>

Homework Hack 2: Find the First and Last Occurrence of an Element

Description: Write a function that uses binary search to find the first and last occurrence(find the index of the) of a given target element in a sorted array. If the element is not present, return -1.

%%html
<script>
arr = [1, 2, 2, 2, 3, 4, 5]
target = 2

function firstLast(arr, target) {
  function findBound(isFirst) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      if (arr[mid] === target) {
        result = mid;
        if (isFirst) {
          right = mid - 1; 
        } else {
          left = mid + 1; 
        }
      } else if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return result;
  }

  const first = findBound(true);
  const last = findBound(false);

  return first === -1 ? -1 : [first, last];
}

console.log(firstLast(arr, target))
</script>

Homework Hack 3: Search for the Smallest Element

Description: You are given a sorted array of integers. Write a function that uses Binary Search to find the smallest element that is greater than or equal to the target. If that an element doesnt exist, return -1.

%%html
<script>
    arr = [1, 3, 5, 7, 9, 11]
    target = 8

function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] >= target) {
      result = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return result === -1 ? -1 : arr[result];
}

console.log(lowerBound(arr, target))
</script>