Tutorial by Examples

Introduction Binary Search is a Divide and Conquer search algorithm. It uses O(log n) time to find the location of an element in a search space where n is the size of the search space. Binary Search works by halving the search space at each iteration after comparing the target value to the middle ...

It's easiest to show a binary search on numbers using pseudo-code int array[1000] = { sorted list of numbers }; int N = 100; // number of entries in search space; int high, low, mid; // our temporaries int x; // value to search for low = 0; high = N -1; while(low < high) { mid = (...

Linear search is a simple algorithm. It loops through items until the query has been found, which makes it a linear algorithm - the complexity is O(n), where n is the number of items to go through. Why O(n)? In worst-case scenario, you have to go through all of the n items. It can be compared to l...

The Rabin–Karp algorithm or Karp–Rabin algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text.Its average and best case running time is O(n+m) in space O(p), but its worst-case time is O(nm) where n is the length of the text and m is the le...

We can have three cases to analyze an algorithm: Worst Case Average Case Best Case #include <stdio.h> // Linearly search x in arr[]. If x is present then return the index, // otherwise return -1 int search(int arr[], int n, int x) { int i; for (i=0; i<n; i...