Algorithms and Data Structures

Primary tabs

Bookmark to learn: Login to use bookmarks.

Statistics

'Repetition is the mother of all learning.'

Bookmark to learn: Login to use bookmarks.

Add to collection ... add Algorithms and Data Structures to your collections:

Help using Flashcards ...just like in real life ;)

  1. Look at the card, do you know this one? Click to flip the card and check yourself.
  2. Mark card Right or Wrong, this card will be removed from the deck and your score kept.
  3. At any point you can Shuffle, Reveal cards and more via Deck controls.
  4. Continue to reveal the wrong cards until you have correctly answered the entire deck. Good job!
  5. Via the Actions button you can Shuffle, Unshuffle, Flip all Cards, Reset score, etc.
  6. Come back soon, we'll keep your score.
    “Repetition is the mother of all learning.”
  7. Signed in users can Create, Edit, Import, Export decks and more!.

Bookmark to learn: Login to use bookmarks.

Share via these services ...

Email this deck:

Right: #
Wrong: #
# Right & # Wrong of #

Linear Search

O(N)

Start from the leftmost element of arr[] and one by one compare x with each element of arr[]

for (int i = 0; i < n.size(); i++)

Binary Search

O(log N)

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}

Jump Search

The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements. The best step size is m = √n.

int jumpSearch(int arr[], int x, int n) // x value to find,n=size

{
int step = sqrt(n); // Finding block size to be jumped
int prev = 0;
while (arr[min(step, n)-1] < x)
{
prev = step;
step += sqrt(n);
if (prev >= n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;
// If we reached next block or end of
// array, element is not present.
if (prev == min(step, n))
return -1;
}
// if element is found
if (arr[prev] == x)
return prev;
return -1;
}