Data Structures & Algorithms

Data Structures & Algorithms - Binary search

author: Paul Kim

categories: dsa, csharp

tags: dsa, csharp

Binary search algorithm

Binary search is an $O(\log n)$ search algorithm that works on sorted arrays. Binary search starts at the middle of the array and continues to search either the left or right half of the array depending on whether the value being searched is less than or greater than the value found in the middle. This effectively halves the search space per each iteration and therefore has better time complexity than just scanning the entire array. There are both recursive and iterative implementations of binary search. Here I list both using C# for reference.

Recursive

public class Program {
  public static void Main(string[] args) {
    int[] arr = { 1, 2, 3, 4, 5 };
    int n = arr.Length;

    Console.WriteLine(BinarySearch(arr, 0, n - 1, 0));
    Console.WriteLine(BinarySearch(arr, 0, n - 1, 1));
    Console.WriteLine(BinarySearch(arr, 0, n - 1, 2));
    Console.WriteLine(BinarySearch(arr, 0, n - 1, 3));
    Console.WriteLine(BinarySearch(arr, 0, n - 1, 4));
    Console.WriteLine(BinarySearch(arr, 0, n - 1, 5));
    Console.WriteLine(BinarySearch(arr, 0, n - 1, 6));
  }

  public static int BinarySearch(int[] input, int min, int max, int n) {
    if (min > max) {
      return -1;
    }

    int mid = (min + max) / 2;
    if (input[mid] < n) {
      return BinarySearch(input, mid + 1, max, n);
    }
    if (input[mid] > n) {
      return BinarySearch(input, min, mid - 1, n);
    }
    return mid;
  }
}

Iterative

public class Program {
  public static void Main(string[] args) {
    int[] arr = { 1, 2, 3, 4, 5 };

    Console.WriteLine(BinarySearch(arr, 0));
    Console.WriteLine(BinarySearch(arr, 1));
    Console.WriteLine(BinarySearch(arr, 2));
    Console.WriteLine(BinarySearch(arr, 3));
    Console.WriteLine(BinarySearch(arr, 4));
    Console.WriteLine(BinarySearch(arr, 5));
    Console.WriteLine(BinarySearch(arr, 6));
  }

  public static int BinarySearch(int[] input, int n) {
    int min = 0;
    int max = input.Length - 1;

    while (min <= max) {
      int mid = (min + max) / 2;
      if (input[mid] < n) {
        min = mid + 1;
        continue;
      }
      if (input[mid] > n) {
        max = mid - 1;
        continue;
      }
      return mid;
    }
    return -1;
  }
}

Notes