Articles by "Searching"
Showing posts with label Searching. Show all posts

at December 22, 2019 0

Max and Min Finding

Here our problem is to find the minimum and maximum items in a set of n elements. We will see two methods here first one is iterative version and the next one uses divide and conquer strategy to solve the problem.

Iterative Algorithm:


MinMax(A,n)

{

max = min = A[0];

for(i = 1; i <n; i++}

{

if(A[i] > max)

max = A[i];

if(A[i] < min}

min = A[i];

}

}


The above algorithm requires 2(n-1) comparison in worst, best, and average cases. The comparison A[i] < min is needed only when A[i] > max is not true. If We replace the content inside the for loop by
if(A[i] >1nax)
max = A[i];
else if(A[i] < min)
m.i_n = A[i];
Then the best case occurs when the elements are in increasing order with (n-1) comparisons and worst case occurs when elements are in decreasing order with 2(n-1) comparisons. For the average case A[i] > max is about half of the time so number of comparisons is 3n/2 — 1.
We can clearly conclude that the time complexity is O[n].

 C Program For Mini Max Search


#include <stdio.h>


#include <stdlib.h>


#include <time.h>


#define SIZE 1000


void MinMax(int *arr, int l, int h, int *max, int *min)


{


    int max1, min1;


    if (l == h) { // case I - only one item


        *max = *min = arr[0];


    }


     else if (l == h - 1) { // case II - when there are two elements


        if (arr[l] > arr[h])


        {


            *max = arr[l];


            *min = arr[h];


        }


        else {


            *max = arr[h];


            *min = arr[l];


        }


    }


     else { // case - III


        int mid = (l + h) / 2; // Divide


        MinMax(arr, l, mid, max , min); // conquer


        MinMax(arr, mid+1, h, &max1 , &min1); //conquer


        if(*max < max1) *max = max1; //combine


        if(*min > min1) *min = min1;  //combine


    }


}


int main(int argc, char const *argv[])


{


    int arr[SIZE], n;


    clock_t start, end;


    double total_time = 0.00;


    int min, max;


    printf("Enter number of elements : ");


    scanf("%d", &n);


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


    {


        arr[i] = rand() % 1000;


    }


    start = clock();


    MinMax(arr, 0, n-1, &max, &min);


    end = clock();


    printf("Min element :  %d\nMax element : %d\n", min, max);


    total_time += (double)(end - start) / CLOCKS_PER_SEC;


    printf("Execution time : %f seconds", total_time);


    return 0;


}

Output

Mini-Max Search


Read more »
no image

at September 29, 2018 0

C++ Program for modular search and linear search using recursion function


Before starting with the program to find binary search and linear search using recursion function let us know about recursion function and Modular Search.


Recursion Function

Recursion is a process by which a function call itself repeatedly until some specified condition has been satisfied.
                
The process is used for repetitive computation in which action is stated in terms of previous result.
                
In order to solve a problem recursively two condition must be satisfied.
  • The problem must be written in a recursive form.
  • The problem statement must include a problem stopping condition.


Modular Search

It is the type of search in which we use mod recursively to find the item which is searched in the program.


C++ Program for linear search using recursion function


#include<iostream>
using namespace std;

int recursiveLinearSearch(int array[],int key,int size)
{
size=size-1;
if(size <0)
{
return -1;
}
else if(array[size]==key){
return 1;
}
else{
return recursiveLinearSearch(array,key,size);
}
}


int main()
{

cout<<"Enter The Size Of Array: ";
int size;
cin>>size;
int array[size], key,i;

// Taking Input In Array
for(int j=0;j<size;j++)
{
cout<<"Enter "<<j<<" Element : ";
cin>>array[j];
}
//Your Entered Array Is
for(int a=0;a<size;a++)
{
cout<<"array[ "<<a<<" ] = ";
cout<<array[a]<<endl;
}
cout<<"Enter Key To Search in Array";
cin>>key;
int result;
result=recursiveLinearSearch(array,key,size--);
if(result==1)
{
cout<<"Key Found in Array ";
}
else{
cout<<"Key NOT Found in Array ";
}
return 0;
}


C++ Program for modular search and using recursion function

#include <iostream>
using namespace std;
int mod (int x, int y, int a)
{
if (x == 0)
return 0;
if (y == 0)
return 1;
// If y is even
long temp;
if (y % 2 == 0) {
temp = mod(x, y / 2, a);
temp = (temp * temp) % a;
}
// If y is odd
else {
temp = x % a;
temp = (temp * mod(x, y - 1, a) % a) % a;
}
return (int)((temp + a) % a);
}
int main()
{
int x,y,a;
cout<<"x^y (mod a)"<<endl;
cout<<"Enter Base Value: ";
cin>>x;
cout<<"Enter Exponent: ";
cin>>y;
cout<<"Enter Modular Value: ";
cin>>a;
long temp;
temp= mod(x,y,a);
cout<<x <<" ^ "<<y <<" (mod "<<a<<")"<<" = "<<temp;
}
Read more »
no image

at September 29, 2018 0

C Program for Binary Search and Merge Search using recursion function

Before starting with the program to find binary search and linear search using recursion function let us know about recursion function.

Recursion Function

Recursion is a process by which a function call itself repeatedly until some specified condition has been satisfied.
                
The process is used for repetitive computation in which action is stated in terms of previous result.
                
In order to solve a problem recursively two condition must be satisfied.
  • The problem must be written in a recursive form.
  • The problem statement must include a problem stopping condition.


C Program for Binary Search and using recursion function

#include <stdio.h>
int binarysearch(int a[], int low, int high, int x)
{
    int mid = (low + high) / 2;
    if (low > high)
        return -1;
    if (a[mid] == x)
        return mid;
    if (a[mid] < x)
        return binarysearch(a, mid + 1, high, x);
    else
        return binarysearch(a, low, mid - 1, x);
}
int main(void)
{
    int a[100];
    int len, pos, search_item;
    printf("Enter the length of the array\n");
    scanf("%d", &len);
    printf("Enter the array elements\n");
    for (int i = 0; i < len; i++)
        scanf("%d", &a[i]);
    printf("Enter the element to search\n");
    scanf("%d", &search_item);
    pos = binarysearch(a, 0, len - 1, search_item);
    if (pos < 0)
        printf("Cannot find the element %d in the array.\n", search_item);
    else
        printf("The position of %d in the array is %d.\n", search_item, pos + 1);
    return 0;
}

C Program for Merge Search using recursion function
#include <iostream>
 
using namespace std;

// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
    // We have low to mid and mid+1 to high already sorted.
    int i, j, k, temp[high - low + 1];
    i = low;
    k = 0;
    j = mid + 1;

    // Merge the two parts into temp[].
    while (i <= mid && j <= high)
    {
        if (a[i] < a[j])
        {
            temp[k] = a[i];
            k++;
            i++;
        }
        else
        {
            temp[k] = a[j];
            k++;
            j++;
        }
    }

    // Insert all the remaining values from i to mid into temp[].
    while (i <= mid)
    {
        temp[k] = a[i];
        k++;
        i++;
    }

    // Insert all the remaining values from j to high into temp[].
    while (j <= high)
    {
        temp[k] = a[j];
        k++;
        j++;
    }

    // Assign sorted data stored in temp[] to a[].
    for (i = low; i <= high; i++)
    {
        a[i] = temp[i - low];
    }
}

// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        // Split the data into two half.
        MergeSort(a, low, mid);
        MergeSort(a, mid + 1, high);

        // Merge them to get sorted output.
        Merge(a, low, high, mid);
    }
}

int main()
{
    int n, i;
    cout << "\nEnter the number of data element to be sorted: ";
    cin >> n;

    int arr[n];
    for (i = 0; i < n; i++)
    {
        cout << "Enter element " << i + 1 << ": ";
        cin >> arr[i];
    }

    MergeSort(arr, 0, n - 1);

    // Printing the sorted data.
    cout << "\nSorted Data ";
    for (i = 0; i < n; i++)
        cout << "->" << arr[i];

    return 0;
}


Program Explanation

  1. Take input of data.
  2. Call MergeSort() function.
  3. Recursively split the array into two equal parts.
  4. Split them until we get at most one element in both half.
  5. Combine the result by invoking Merge().
  6. It combines the individually sorted data from low to mid and mid+1 to high.
  7. Return to main and display the result.
  8. Exit.
Read more »

at March 09, 2018 0

C Program For Binary Search

#include<stdio.h>

int main()
{
    int a[100],i,n,item,flag=0,low,high,mid,j,temp;
    printf("How many numbers\n");
    scanf("%d",&n);
    printf("Enter the value in array:-\n");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<n-1;i++)
    {
        for (j=i+1;j<n;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    printf("Enter item to be searched:\n");
    scanf("%d",&item);
    low=0;
    high=n-1;
    do
    {
        mid=(low+high)/2;
        if(item>a[mid])
        {
            low=mid+1;
            flag=0;
        }
        else if (item<a[mid])
        {
            high=mid-1;
            flag=0;
        }
        else
        {
            flag=1;
            break;
        }
    }
    while(item!=a[mid]&&low<=high);
    if(flag==1)
        printf("\nItem found");
    else
        printf("\nItem not found");
    return 0;
}

OUTPUT

C Program For Binary Search

Read more »

at March 05, 2018 0

Linear search in C Programming

Linear search in C programming: The following code implements linear search (Searching algorithm) which is used to find whether a given number is present in an array and if it is present then at what location it occurs. It is also known as sequential search. It is straightforward and works as follows: We keep on comparing each element with the element to search until it is found or the list ends. Linear search in C language for multiple occurrences and using function.





Linear search C program 

span style="color: #339933;">#include<stdio.h>


int main()
{
int array[100], search, c, n;

printf("Enter the number of elements in array\n");
scanf("%d",&n);

printf("Enter %d integer(s)\n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter the number to search\n");
scanf("%d", &search);

for (c = 0; c < n; c++)
{
if (array[c] == search) /* if required element found */
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
if (c == n)
printf("%d is not present in array.\n", search);

return 0;
}
Download Linear search program.
Output of program:
linear Search in C
C program for binary search

Linear search for multiple occurrences

In the code below we will print all the locations at which required element is found and also the number of times it occur in the list.
#include<stdio.h>

int main()
{
int array[100], search, c, n, count = 0;

printf("Enter the number of elements in array\n");
scanf("%d", &n);

printf("Enter %d numbers\n", n);

for ( c = 0 ; c < n ; c++ )
scanf("%d", &array[c]);

printf("Enter the number to search\n");
scanf("%d", &search);

for (c = 0; c < n; c++) {
if (array[c] == search) {
printf("%d is present at location %d.\n", search, c+1);
count++;
}
}
if (count == 0)
printf("%d is not present in array.\n", search);
else
printf("%d is present %d times in array.\n", search, count);

return 0;
}
Download Linear search multiple occurrence program.
Output of code:
linear Search in C for multiple occurrence

C program for linear search using function

#include<stdio.h>

long linear_search(long [], long, long);

int main()
{
long array[100], search, c, n, position;

printf("Input number of elements in array\n");
scanf("%ld", &n);

printf("Input %d numbers\n", n);

for (c = 0; c < n; c++)
scanf("%ld", &array[c]);

printf("Input number to search\n");
scanf("%ld",&search);

position = linear_search(array, n, search);

if (position == -1)
printf("%d is not present in array.\n", search);
else
printf("%d is present at location %d.\n", search, position+1);

return 0;
}

long linear_search(long a[], long n, long find) {
long c;

for (c = 0 ;c < n ; c++ ) {
if (a[c] == find)
return c;
}

return -1;
}


Read more »
Subscribe to: Posts (Atom)