The SDET Playbook

← All questions

Implement binary search in TypeScript, then show the tests that prove it works

Asked Sep 28, 2026Viewed 0 times

1 Answer

Sign in to answer and to vote.

  • 0
    The SDET PlaybookSep 28, 2026

    Write a correct implementation quickly, then spend your effort on the tests, because that's what an SDET interview is really probing.

    /** Returns the index of target in a sorted array, or -1 if it is absent. */
    export function binarySearch(sorted: readonly number[], target: number): number {
      let low = 0;
      let high = sorted.length - 1;
    
      while (low <= high) {
        const mid = low + Math.floor((high - low) / 2);
        if (sorted[mid] === target) return mid;
        if (sorted[mid] < target) low = mid + 1;
        else high = mid - 1;
      }
      return -1;
    }
    

    It runs in O(log n) time and O(1) space. A recursive version is equally valid: it only recurses about log₂ n levels deep, around 50 even for the largest arrays, so stack depth isn't a real concern. Pick whichever you can write without off-by-one mistakes.

    Then test the edges, where binary search usually breaks:

    import { describe, expect, it } from 'vitest';
    import { binarySearch } from './binarySearch';
    
    describe('binarySearch', () => {
      it('returns -1 for an empty array', () => expect(binarySearch([], 3)).toBe(-1));
      it('finds the only element', () => expect(binarySearch([3], 3)).toBe(0));
      it('finds the first and last elements', () => {
        expect(binarySearch([1, 3, 5, 7], 1)).toBe(0);
        expect(binarySearch([1, 3, 5, 7], 7)).toBe(3);
      });
      it('returns -1 below, between and above the values', () => {
        for (const target of [0, 4, 8]) expect(binarySearch([1, 3, 5, 7], target)).toBe(-1);
      });
      it('finds every element of an even- and an odd-length array', () => {
        for (const arr of [[1, 2, 3, 4], [1, 2, 3, 4, 5]]) {
          arr.forEach((value, index) => expect(binarySearch(arr, value)).toBe(index));
        }
      });
      it('returns an index holding the target when values repeat', () => {
        const arr = [1, 2, 2, 2, 3];
        expect(arr[binarySearch(arr, 2)]).toBe(2);
      });
    });
    

    Say out loud what you're covering and why: empty and single-element inputs, both ends, misses on every side, even and odd lengths (where the midpoint rounding matters), and duplicates, where the contract says "an index", not "the first index". Also name what the function assumes, a sorted input, and ask whether it should validate that or leave it to the caller.

    Sources: Wikipedia: binary search, Vitest