Binary Search 3-Sum

Fun Fact: Binary search has been notoriously tricky to get right. The first binary search was published in 1946 however the first bug-free binary search was published in 1962.

A binary search assumes a sorted data set and takes conditions to search by halving the set and comparing until there is a match or a match is not found. The key comparison operators for the target and set are.

• Lower
• Higher
• equal to
• not equal to.

Below is a standard Java implementation (Noting it’s often implemented recursively)

public static int binarySearch(int[] a, int key){
  int lo = 0, hi = a. length-1;
  while (lo <= hi){
    int mid = lo + (hi - lo) / 2;
    if      (key < a[mid]) hi = mid - 1;
    else if (key > a[mid] ) lo = mid + 1;
    else return mid;
  }
  //no match
  return -1;
}

Mathematical Analysis - Binary Search

Proposition: Binary search uses at most 1 + lg N compares to search in a sorted array of size N

Definition: T(N) = # compares to binary search in a sorted subarray of size < N

Binary search recurrence: T(N) <= T(N/2) + 1 for N > 1, with T(1) = 1

Proof Sketch (only holds if $N^{2}$):

• T(N) < = T(N/2) + 1 Given
• <= T(N / 4) + 1 + 1 Apply recurrence to first term
• <= T(N / 8) + 1 + 1 + 1 Apply reccurence to first term
• …
• <= T(N / N) + 1 + 1 + … + 1 Stop applying T(1) = 1
• = 1 + lg N

Faster Algorithm for 3-Sum

Sort based algorithm

• Sort the N (Distinct Numbers)
• For each pair of numbers a[i] and a[j] do a binary search for -(a[i] + a[j])

Analysis : Order of growth is $N^{2} log N$

• Step 1: $N^{2}$ with insertion sort
• Step 2: $N^{2} log N$ with Binary Search

public static int threeSum(int[] a, int target){
  n = a.length;
  // bubble sort
  for(int i = 0; i < n - 1; i ++){
    for (int j = 0; j < n - i - 1; j++){
      if(a[j] > a[j + 1])}{
        int temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }
    }
  };
  // Binary Complement search
  for ( int i = 0; i < n - 2; i ++){
    for (int j = i + 1; j < n - 1; j ++){
      int complement = target - a[i] - a[j];
      int low = j + 1;
      int hi = n - 1;
      while (low <= hi){
        int mid = low + (hi - low) / 2;
        if      (complement < a[mid]) hi = mid - 1;
        else if (complement > a[mid]) low = mid + 1;
        else return true;
      }
    }
  }
  //no match
  return false;
}