Binary search

3 snippets across 2 stacks — Interview Prep, Bash & Linux

Also written as locate binary

DSAInterview Prep

O(log n) — Logarithmic Time

syntax

Each step halves the remaining work. Classic sign: dividing the problem space in two.

example

// JavaScript
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

# Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

output

Time: O(log n) | Space: O(1)

Note Balanced BST operations are O(log n). Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2 to prevent integer overflow. If you see 'sorted array' in a problem, think binary search immediately.

Binary Search on Sorted Array

DSA · Arrays & Strings

syntax

lo = 0, hi = length - 1
while lo <= hi:
  mid = lo + (hi - lo) // 2
  compare and adjust lo or hi

example

// JavaScript
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

# Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

output

binary_search([1,3,5,7,9,11], 7) → 3

Note Time O(log n), Space O(1). Off-by-one errors are the #1 bug — practice until the template is muscle memory. Use lo <= hi when searching for exact match. Use lo < hi when narrowing to a single candidate. Always test with 0, 1, and 2 element arrays.

SHBash & Linux

Locate Installed Binaries

SH · Package Management

syntax

which command
whereis command
command -v command

example

which python3
whereis gcc
command -v node || echo 'node not found'

output

/usr/bin/python3
gcc: /usr/bin/gcc /usr/lib/gcc /usr/share/man/man1/gcc.1.gz

Note which shows the full path of a command. whereis also shows man pages and source locations. In scripts, prefer command -v over which because it is POSIX-compliant and handles aliases/builtins correctly.