Data Structures and Algorithms - Searching

What is Data?

Data is anything that conveys bits of information. Data can not only be in text, it can be images, videos and audio.

And whatever we infer from data is information.

So data Structure is basically way to store/interact with data in a structured manner

What is algorithm?

Finite number of steps which togehter solve a problem.

What we will learn throughout the class?

• Arrays - searching and sorting algorithms
• Stacks - push and pop algorithms
• Queues - insert and delete
• Linked Lists - insert and delete
• Trees - traversal, insertion, deletion, balance
• Graphs - traversal, insertion, deletion, balance

Exercise 1 - recap - write a code in C to take 5 elements for and array and find the average of those numbers

#include <stdio.h>

int main(){
    int a[5], s=0, i;
    float avg;
    printf("Enter the elements of the array: ");
    for(i = 0; i<5; i++){
        scanf("%d",&a[i]);
    }
    //make sum
    for(i = 0; i<5; i++){
        s += a[i];
    }
    avg = s / 5.0;
    printf("The average is: %f", avg);
    return 0;
}

Linear search vs Binary search

Linear search, we travers through the elements 1 by 1 and then say the index of the element we are searching or say the element is not found.

Let’s say the we have the following array -

5 2 3 4 9

and we are trying to find the element 9.

Then it will go through all the elements and then return the index 4.

So in the worst case we need to go through all the n elements of the array giving us the worst case complexity of O(n)

There is where we get to Binary search, the only criteria we need is the array needs to be sorted.

For binary search we go to the middle, if the element we are searching is greater than the middle we search the right side with the same strategy or if it is less than then we search the left side with same strategy, otherwise we have found the element. This goes on until we have no middle to find.

Now lets take this following array and do a binary search for the element 9

1 2 3 4 6 7 8 9

The middle of this array is index 3 with the value 4 and 9 is greater than 4 so now we will search the following array -

6 7 8 9

Now the middle here is the index 1 with the value 7 which is less than 9 so we search out the following array -

8 9

Same process we getting the array -

9

We find 9 here.

Code for binary search

#include <stdio.h>

int main(){
    int a[10],x, start=0, end=9, middle;
    middle = (start + end) / 2;
    printf("Enter the elements of the array: ");
    for(i = 0; i<10; i++){
        scanf("%d",&a[i]);
    }
    printf("Enter the element to search: ");
    scanf("%d",&x);
    //find element
    while(start <= end){
        if(x < a[middle]){
            end = middle - 1;
        }
        else if(x > a[middle]){
            start = middle + 1;
        }
        else{
            printf("The element is found at index %d", middle);
        }
        middle = (start + end) / 2;
    }
    if(start > end){
        printf("Element not found");
    }
    return 0;
}