wait, wut?

Sorting and Searching Algorithms

Sorting and Searching Algorithms

Bubble Sort


Selection Sort


Insertion Sort


Merge Sort


Quicksort


Counting Sort


Radix Sort


Bucket Sort


Heap Sort


Shell Sort


  • sequential searching algorithm
  • start from one end and check every element of list until desired element is found
    • for loop that returns when/if element is found

  • searching algorithm for finding element's position in sorted array
  • element is always searched in middle of a portion of an array

NOTE: binary search can only be implemented on a sorted list of items. if elements are not sorted already, need to sort them first.

Binary Search Working

Binary search algorithm can be implemented in two ways

  1. iterative method
  2. recursive method
    • follows divide and conquer approach

general steps:

  • Step 1:
    • given array:

Initial array - element to be searched is x = 4

  • Step 2:
    • set two pointers low and high at the lowest and highest positions

Setting pointers

  • Step 3:
    • find middle element mid of array (i.e. arr[(low + high)/2] = 6)

Mid element

  • Step 4:
    • if x == mid, return mid.
    • Else, compare element to be searched with mid
  • Step 5:
    • if x > mid, compare x with middle element of elements on right side of mid
    • this is done by setting low to low = mid + 1
  • Step 6:
    • else, compare x with middle element of elements to left side of mid
    • this is done by setting high to high = mid - 1

Finding mid element

  • Step 7:
    • repeat steps 3 to 6 until low meets high

Mid element

  • Step 8:
    • x = 4 is found

Found


Binary Search Algorithm Pseudocode

Iterative Method

do until the pointers low and high meet each other
    mid = (low + high)/2
    if (x == arr[mid]) {
        return mid
    } else if (x > arr[mid]) { // x is on right side
        low = mid + 1
    } else { // x is on left side
        high = mid - 1
    }

Recursive Method

binarySearch(arr, x, low, high) {
    if (low > high) {
        return false
    } else {
        mid = (low + high) / 2
        if (x == arr[mid]) {
            return mid
        } else if (x > arr[mid]) { // x is right side
            return binarySearch(arr, x, mid + 1, high)
        } else { // x is on left side
            return binarySearch(arr, x, low, mid - 1)
        }
    }
}

Implementations

Iterative

Python

 
def binarySearch(array, x, low, high):
    # Repeat until the pointers low and high meet each other
    while low <= high:
        mid = low + (high - low)//2

        if array[mid] == x:
            return mid

        elif array[mid] < x:
            low = mid + 1

        else:
            high = mid - 1

    return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

C++

 
#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {

	// Repeat until the pointers low and high meet each other
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}

Java

 
class BinarySearch {
  int binarySearch(int array[], int x, int low, int high) {

    // Repeat until the pointers low and high meet each other
    while (low <= high) {
      int mid = low + (high - low) / 2;

      if (array[mid] == x)
        return mid;

      if (array[mid] < x)
        low = mid + 1;

      else
        high = mid - 1;
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int array[] = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;
    int x = 4;
    int result = ob.binarySearch(array, x, 0, n - 1);
    if (result == -1)
      System.out.println("Not found");
    else
      System.out.println("Element found at index " + result);
  }
}

Recursive

Python

 
def binary_search(array, x, low, high):
    if high >= low:
        mid = low + (high - low)//2

        # If found at mid, then return it
        if array[mid] == x:
            return mid

        # Search the left half
        elif array[mid] > x:
            return binary_search(array, x, low, mid - 1)

        # Search the right half
        else:
            return binary_search(array, x, mid + 1, high)

    return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binary_search(array, x, 0, len(array) - 1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

C++

 
#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // If found at mid, then return it
    if (array[mid] == x)
      return mid;

    // Search the left half
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);

    // Search the right half
    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}

Java

 
class BinarySearch {
    int binarySearch(int array[], int x, int low, int high) {

        if (high >= low) {
            int mid = low + (high - low) / 2; // TODO: why add low too?

            if (array[mid] == x) {
                return mid;
            } else if (array[mid] > x) {
                return binarySearch(array, x, low, mid - 1);
            } else {
                return binarySearch(array, x, mid + 1, high);
            }
        }

        return -1;
    }

    public static void main(String args[]) {
        BinarySearch ob = new BinarySearch();
        int array[] = { 3, 4, 5, 6, 7, 8, 9 };
        int x = 4;
        int result = ob.binarySearch(array, x, 0, array.length - 1);
        if (result == -1) {
            System.out.println("Not found");
        } else {
            System.out.println("Element found at index " + result);
        }
    }
}

Binary Search Complexity

Time Complexities

  • best case: O(1)
  • average case: O(log n)
  • worst case: O(log n)

Space Complexity

  • O(1)

Binary Search Applications

  • in libraries of Java, .Net, C++ STL
  • while debugging, binary search is used to pinpoint place where error happens
Made with Gatsby G Logo