DSA: 03-Jan

1) Linear search

// linear search

#include <stdio.h>

int main()

{

    int size=0;

    int index = -1;

    int element;

    printf("Enter size of array: ");

    scanf("%d", &size);

    printf("Enter elements of array: ");

    int arr[size];

    int i=0;

    for(i=0; i< size; i++){

        scanf("%d", &arr[i]);

        // printf("Elements of arr: %d", arr[i]);

    }

    printf("Element to search:");

    scanf("%d", &element);

    for(i=0; i< size; i++){

        if(arr[i] == element){

            index = i;

            printf("element found at index%d", index);

            return index;

        }

    }

    

    printf("enter a valid element");

    return 0;

}

2) Binary search

// linear search

#include <stdio.h>

void swap(int* xp, int* yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

 

// Function to perform Selection Sort

void selectionSort(int arr[], int n)

{

}

int main()

{

    int size=0;

    int index = -1;

    int element;

    printf("Enter size of array: ");

    scanf("%d", &size);

    printf("Enter elements of array : ");

    int arr[size];

    int i=0;

    for(i=0; i< size; i++){

        scanf("%d", &arr[i]);

        // printf("Elements of arr: %d", arr[i]);

    }

    printf("Element to search:");

    int k, j, min_idx;

 

    // One by one move boundary of unsorted subarray

    for (k= 0; k < size - 1; k++) {

 

        // Find the minimum element in unsorted array

        min_idx = k;

        for (j = k + 1; j < size; j++)

            if (arr[j] < arr[min_idx])

                min_idx = j;

 

        // Swap the found minimum element

        // with the first element

        swap(&arr[min_idx], &arr[k]);

    }

    return 0;

}

------> Single code----->>>>

#include <stdio.h>

void swap(int* xp, int* yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

 

void sort(int arr[], int size)

{

        int k, j, min_idx;

 

    

    for (k= 0; k < size - 1; k++) {

 

    

        min_idx = k;

        for (j = k + 1; j < size; j++)

            if (arr[j] < arr[min_idx])

                min_idx = j;

        swap(&arr[min_idx], &arr[k]);

    }

}

int findMean(int first, int last)

{

    if((first+last)%2 != 0){

        return (first+last+1)/2;

    } else {

      return (first+last)/2;  

    }

}

void binarySearch(int arr[], int size, int element)

{

    sort(arr, size);

    int first = 0, last = size , mean = findMean(first, last);

    

    while(first< last){

     if(element>arr[mean]){

        first = mean;

        mean = findMean(first, last);

    } else if(element == arr[mean])

    {

        printf("Element found at index : %d", mean);

        return ;

    } else {

        last= mean;

        mean = findMean(first, last);

    }

    };

     printf("Not found! Enter a valid element");

}

void linearSearch(int arr[], int size, int element)

{

        for(int i=0; i< size; i++){

        if(arr[i] == element){

            printf("element found at index%d : ", i);

            return ;

        }

    }

    printf("Not found! Enter a valid element");

}

int main()

{

    int size=0, index = -1,  element;

    printf("Enter size of array: ");

    scanf("%d", &size);

    printf("Enter elements of array : ");

    int arr[size];

    int i=0;

    for(i=0; i< size; i++){

        scanf("%d", &arr[i]);

    }

    printf("Element to search:");

    scanf("%d",&element);

    //linearSearch(arr,size, element);  // for linearSearch

    binarySearch(arr, size, element);  // for binarySearch

    return 0;

}