Searching Algorithms (linear search, binary search)

What crucial prerequisite must be met for binary search to work correctly?

function binarySearch(arr, 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;
    if(arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Array must be empty
Array must be sorted
Binary search requires sorted input because: 1) Relies on comparing middle element to determine search direction, 2) Eliminates half of remaining elements each iteration, 3) Assumes elements to left are smaller and right are larger, 4) Cannot make valid comparisons on unsorted data, 5) Time complexity of O(log n) depends on this property, 6) Sorting requirement is crucial for algorithm correctness, 7) Most efficient when array maintains sorted state, 8) Common source of bugs when prerequisite not met.
Array must contain numbers only
Array must have odd length

Next Question (2/24)