home

Binary Search

Table of Contents

Given a sorted array, find the index of element t

#include <stdio.h>

int binary_search(int *arr, int size, int t) {
  int start = 0;
  int end = size - 1;

  while (start <= end) {
    int mid = (start + end) / 2;

    if (arr[mid] == t) {
      return mid;
    } else if (arr[mid] > t) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  return -1;
}

int main() {
  int arr[] = {1, 10, 69, 420, 900};
  int size = sizeof(arr) / sizeof(int);

  int idx = binary_search(arr, size, 420);

  printf("%d", idx);
}

TODO A note on increasing functions

  • binary search can be used not just on arrays but any increasing (or decreasing function)
  • Use yes/no method to simplify

Lower bound and upper bound

  • lower bound: Find an element greater than or equal to x.-
  • upper bound: Find an element strictly greater than x.
#include <stdio.h>

int lower_bound(int *arr, int size, int x) {
  int start = 0;
  int end = size - 1;

  while (start <= end) {
    int mid = (start + end) / 2;

    if (arr[mid] >= x) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  return start;
}

int upper_bound(int *arr, int size, int x) {
  int start = 0;
  int end = size - 1;

  while (end - start > 1) { // while at least 3 elements
    int mid = (start + end) / 2;

    if (arr[mid] > x) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }

  if (arr[start] > x) return start;
  else if (arr[end] > x) return end;
  else return size;
}

int main() {
  int arr[] = {1, 4, 5, 5, 5, 6, 9, 9, 10};
  int size = sizeof(arr) / sizeof(int);

  int res = upper_bound(arr, size, 1);

  if (res != size)
    printf("%d ", arr[res]);
}

Frequency of a number in sorted array

upperbound() - lowerbound()

Discrete binary search

Find smallest x such that x3 > v example: v = 100; x = 5 

#include <stdio.h>

// Find smallest =x= such that x^3 > v
// example: v = 100; x = 5

int solve() {
  int v = 100;

  int lo =  1;
  int hi = v;

  while (hi - lo > 1) {
    int mid = (lo + hi) / 2;

    if (mid * mid * mid > v) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }


  if (lo * lo * lo > v) return lo;
  else if (hi * hi * hi > v) return hi;
  else return -1;
}

int main() {
  printf("%d ", solve());
}

Author: Siddhant Kumar