Binary Search

Binary search is one the simplest search algorithms(most are pretty simple) to implement. However, first it assumes an important property of an array that isn't always true; the array is sorted. This search is based on the number of elements(length), and we fold the array in half each time, which makes search time logarithmic.

First, you see in the diagram above that the list is already sorted. Next, we label the first index as the lowest number(LO), the last index as the highest number(HI), and the middle index as the index between lowest and highest(MID). Keep in mind that these are just markers for indices and we aren't moving any of the array elements around.

In the diagram that's searching for the number 16 and we realize that the number 16 is smaller than the number in index MID. As a result, we move the high index right before the mid index, and we reorganize the mid index as the middle of lo and hi again. This is what cuts the array in half, and in another half every time it checks MID. The resulting indices is represented in the second row of the diagram.

The last row of the diagram, just shows that when we check MID again here we find that it matches our search number, and thus re return the MID index and we are doneeeeee!!!!

In the case that the number we are searching for is higher than MID, then we'd move LO right after MID and re-position MID. Also, in the case that we don't find any numbers, we'd just return -1.

We repeat these steps several times, folding HI and LO in halves until we've either found our number or we've looked through all the possible index elements.

Here's how it would look in java:

import java.util.Arrays;

class BinarySearch{
.
.
.
    public static int rankIndices(int key, int[] a){
        //assume here that the array is sorted already
        int lo = 0; //index 0 is lowest
        int hi = a.length - 1;                      //and the last index is highest
        while(lo <= hi){                         //stop when hi and lo have become the same index number
            int mid = lo + (hi - lo) / 2;           //find the middle of hi and lo
            if (key < a[mid]) hi = mid - 1;      //key is between mid and lo, move hi before mid
            else if (key > a[mid]) lo = mid + 1; //key is between mid and hi, move low after mid
            else return mid;                        //The middle number is the number we look for
        }
        return -1;
    }
}

And here's some python:

def binarySearch(key, a):
    ## assume that the array is already sorted
    lo = 0
    hi = len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  ##postion mid, integer division
        if key < a[mid]:
            hi = mid - 1           ##key is between mid and low, move hi before mid
        elif key > a[mid]:
            lo = mid + 1           ##key is between mid and hi, move lo after mid
        else:
            return mid             ##mid is where our number resides
    return -1                      ##number is not found


print binarySearch(2, [0, 1, 2, 3, 4, 5, 6, 7]) ##just a test

Read More

Breadth-First Search

Breadth-first search is a search algorithm to find something in an tree. This search algorithm utilizes a queue to keep track of all the nodes that the algorithm will explore. If you're not sure what a queue is then you should take a look at it here.

What basically happens:
The search algorithm starts at the root node(A), and looks at each node of its children before going on.

What specifically happens:
Let's say that the goal is to find E.
The search tree starts at the root node(A) added into the queue then popped, and adds it's children into the queue. If the node it is at is not a goal, it enqueues its children into the queue. If it is the goal then the algorithm returns and stops. Here are some of the steps:

1. We start with A dequeued from the queue. Since A is not the goal and it has children, A's children are enqueued. Queue = [B, C]

2. B is dequeued from the queue and its children are enqueued. Queue = [C, D, E]

3. C is dequeued from the queue and its children are enqueued. Queue = [D, E, F, G]

4. D is dequeued from the queue and its children are enqueued. Queue = [E, F, G, H, I]

5. E is dequeued from the queue and it is our goal, so we stop.

Think about if we are searching for M. What would our path be and what would happen?

Why don't we need an explored list compared to Depth-first algorithm?
Because we search everything level by level, there is no need to keep track of explored nodes, whereas Depth-first has to go back up the tree.

Read More

Depth-First Search

Depth-first search is a search algorithm to find something in an tree. This search algorithm utilizes a stack to keep track of all the nodes that the algorithm will explore. If you're not sure what a stack is then you can read about it here.

What basically happens:
The search starts at the root node(A), and continues to travel down until it reaches a leaf node. Once it hits a leaf node, it goes a step until it can travel downwards again. This continues until it has either found what it was looking for, or until it has explored all of the nodes and found nothing. The path happens this way: (A, B, D, H, I, E, J, K, C, F, L, G)


What specifically happens:
Let's say our goal is to find G.
The search starts with the root node(A) and pushed into the stack, and continues to travel down until it reaches a leaf node. A leaf node is a node that does not have any children. At every step it checks to see if the node has already been explored. If it has been explored, it is simply ignored and continues looking in the stack. If the node has not been explored, it adds any children(that have not been explored) into the stack and adds itself to the explored list. If it hasn't found the goal, then it continues to search until it has found the goal or that the tree is all explored. Here are some of the steps:

1. A goes down B, D, and stops at H.  Explored list = [A, B, D, H]  Stack = [C, E, I]

2. H is a leaf so it doesn't add any children to the stack, I is popped off and added to the explored list.
    Explored list = [A, B, D, H, I]  Stack = [C, E]

3. I also doesn't have any children to add to stack, E gets popped off. It's added to explored and its children added to the stack.
    Explored list = [A, B, D, H, I, E]  Stack = [C, K, J]

4. J is popped off the stack. Because it is a leaf no children are added to the stack. Same thing happens with K.
    Explored list = [A, B, D, H, I, E, J, K]   Stack = [C]

5. C is popped off the stack and any of its unexplored children are added to the stack.
    Explored list = [A, B, D, H, I, E, J, K, C]  Stack = [G, F]

6. F is popped off the stack and, any unexplored children added.
    Explored list = [A, B, D, H, I, E, J, K, C, F]   Stack = [G, L]

7. L is popped off the stack and there are no children to add to the stack.
    Explored list = [A, B, D, H, I, E, J, K, C, F, L]   Stack = [G]

8. G is popped off the stack and because our goal was to find G, we stop our search.

Imagine that there is a search for M. What would happen? The algorithm should return something that signifies nothing was found.

Why do we need an Explored list?
The reason that we would need an explored list is to prevent already traversed nodes from being rechecked, and prevent its children from being added back into the stack. Without the explored list the algorithm would end up in a loop forever.
Just like looking for something in the grocery store, you wouldn't want to go back to an aisle you already looked in, because you remember that you've looked there already.

I hope this clears up any muddy ideas you have about this search algorithm. Feel free to let me know if I've made any errors, grave or not.

Read More

Data Structures - Stacks and Queues

In this post we'll go over some things about stacks and queues.
I have in an earlier post wrote an implementation of a queue while explaining lists. You can take a look here.

Queues:
Queues are FIFO, meaning first in first out. The first element put into the queue is dequeued in the before the others. There is a head and a tail that keeps track of the first and last element enqueued.

Priority queues:
Priority queues are used in storing processes and their priorities. When a system has to switch the processor between many many processes going on, it can switch based on priorities. Some processes have lower priority and some, higher.

Circular Queues:
Circular queues are the same as queues, except that it wraps around the end to the beginning again. With circular queues, it would be easy to use an array, since there is only a limited amount of space in a circle.

Stacks:
Stacks are FILO, meaning first in last out. Think of the stack like, a stack of plates. If you stack one plate over another, say five plates, you would take each one off one by one from the fifth one you stacked to the first one at the very bottom. Stacks are used for memory storage in systems, can be allocated for a process.

These two data structures, as you can see my examples of them, are used in important systems and programs.

Read More

Data Structures - Linked Lists Part 2 (and Queues)

This is a second part to my first post about Arrays and Linked lists. Here I have (finally) implemented and tested two separate queues. Notice that you probably wouldn't need a queue structure if you are utilizing only one queue. The queue structure is so that I can use several different queues. Lots and lots of comments to guide you through:

#include <stdio .h>
#include <stdlib .h>

typedef struct mynode{ //this is the node structure, which includes a data int
  int data;            //and a pointer to the next node
 struct mynode* next;
}node;

typedef struct{ //this is the queue structure, which includes a head and tail pointer.
  node* head;   //a head and a tail pointer points to the first and last nodes of a queue
  node* tail;
}queue;

void enqueue(queue* que, int new_data); //here a list of the function prototypes
void dequeue(queue* que);
int take_queue_data(queue* que);
void print(queue* que);

int main()  //main function to test out
{
    //test cases hereeee
    queue* testq1 = (queue*)malloc(sizeof(queue));
    queue* testq2 = (queue*)malloc(sizeof(queue));
    enqueue(testq1, 1); print(testq1);
    enqueue(testq2, 2); print(testq2);
    enqueue(testq1, 3); print(testq1);
    enqueue(testq2, 4); print(testq2);
    enqueue(testq1, 5); print(testq1);
    enqueue(testq2, 6); print(testq2);
    dequeue(testq1); print(testq1);
    dequeue(testq2); print(testq2);
    dequeue(testq1); print(testq1);
    dequeue(testq2); print(testq2);
    dequeue(testq1); print(testq1);
    dequeue(testq2); print(testq2);
}

void enqueue(queue* que, int new_data){
  node* tmp = (node*)malloc(sizeof(node)); //make a temporary node
  tmp->data = new_data; //set the node->data to what we want to insert   
  tmp->next = NULL; //the next of that node would just be the nothing.

  if (que->head == NULL && que->tail == NULL){// if queue is empty
    que->head = tmp;// here we set the head and tail to this one node
    que->tail = tmp;// because this is the first node ever
  }
  else{ //if queue isnt empty, then just set it as the new tail.
    (que->tail)->next = tmp; 
    que->tail = tmp;// and then remember to link this node to the last one's "next" pointer
  }
  return;
}//end of enqueue

void dequeue(queue* que){
    node* tmp = que->head; //temporary for head of queue
  if (que->head == NULL){ //in case queue is empty
  printf("Queue is empty! \n");
    return;
  }
  else if(que->head == que->tail){
    que->head = NULL; //delete that last element
    que->tail = NULL; //and everything back to NULL
  }
  else{//there is more than one element in queue
      que->head = (que->head)->next;
  }
  free(tmp); //we cant hold on to this mem space forever, or cannnnn we. :(
}// end of dequeue

int take_queue_data(queue* que){//this will give us the first data in queue
    if(que->head == NULL){
     printf("Queue is empty, nothing to look at.");
     return 0;
    }
    else{
     return (que->head)->data;   
    }
}

void print(queue* que){//this is to look at whole queue
    node* tmp = que->head; //set tmp to the front of the queue to walk
    while(tmp != NULL){
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }    
    printf("\n");
}

I hope this helps you understand a linked list better(or how to implement it). Remember there is a doubly linked list too, and it's simple to implement with a alittle tweaking of this code. :D
If you see any problems, have any suggestions, or have any questions feel free to ask in the comments below!

Read More

Data Structures - Arrays and Linked Lists

An array is a random access data structure, while a linked list is a sequential access data structure. So, what's the difference between random and sequential?

Well, random means you can access something directly, and sequential means in order to access something, you have to go one by one. See this:

Arrays:

Linked lists:

or

The differences between the two different linked lists, we'll talk about later. But the difference between arrays and linked lists, we will talk about :D

Okay, the difference: Arrays, can be access directly, like some array A and some index -> A[0].

In the above example of an array, A[0] would = 10, A[1] = 6,  A[2] = 7, and so on. The way to access these indices is very direct, like opening a book to a specific page, assuming that there's bookmarks to every page...

Linked lists on the other hand, are linked someway, the first one in only one direction. For the first linked list, it is analogous to......to.......... walking into a huge cave and every step you get a boulder behind you, you can't go back, sadly.

The second one is linked bidirectionally, which means you can go back and forth between elements, like a string of rooms each with a door. 

Yup, that's all.

I'll add more to this if I find that I have left anything out, and I hope this explains to you arrays and linked lists!

Here's to part 2: Implementation

Read More