DataStructureAndAlgorithms by Win Htut

1 . linearSerach.cpp

/* C++ Program - Linear Search */

#include<iostream>
#include<conio.h>
void main()
{
	
	int arr[10], i, num, n, c=0, pos;
	cout<<"Enter the array size : ";
	cin>>n;
	cout<<"Enter Array Elements : ";
	for(i=0; i<n; i++)
	{
		cin>>arr[i];
	}
	cout<<"Enter the number to be search : ";
	cin>>num;
	for(i=0; i<n; i++)
	{
		if(arr[i]==num)
		{
			c=1;
			pos=i+1;
			break;
		}
	}
	if(c==0)
	{
		cout<<"Number not found..!!";
	}
	else
	{
		cout<<num<<" found at position "<<pos;
	}
	getch();
}

2.binarySerach.cpp

#include<iostream>
#include<conio.h>
using namespace std;
int main()
{

	int n, i, arr[50], search, first, last, middle;
	cout<<"Enter total number of elements :";
	cin>>n;
	cout<<"Enter "<<n<<" number :";
	for (i=0; i<n; i++)
	{
		cin>>arr[i];
	}
	cout<<"Enter a number to find :";
	cin>>search;
	first = 0;

	// { 1 , 2, 3, 4, 5, 6}


	last = n-1;//5 last = 5 
	middle = (first+last)/2; // middle = 2 

	while (first <= last)// 3 <= 5 
	{
		if(arr[middle] < search)//m=2
		{
			first = middle + 1;//3

		}
		else if(arr[middle] == search)
		{
			cout<<search<<" found at location "<<middle+1<<"\n";
			break;
		}
		else
		{
			 last = middle - 1;
		}
		middle = (first + last)/2;
	}
	if(first > last)
	{
		cout<<"Not found! "<<search<<" is not present in the list.";
	}
	getch();
	return 0;
}

3.JumpSerach.cpp

#include <bits/stdc++.h>
#include<iostream>
using namespace std;

int jumpSearch(int arr[], int x, int n)
{
    // Finding block size to be jumped
    int step = sqrt(n);
    cout<<"step"<<step<<endl;//4

    // Finding the block where element is
    // present (if it is present)
    int prev = 0;
    while (arr[min(step, n)-1] < x)//arrr=7
    {
        prev = step;//prev=8
        step += sqrt(n);//step=12
        if (prev >= n)
            return -1;//right 
    }

    // Doing a linear search for x in block
    // beginning with prev.
    while (arr[prev] < x)//55   arr=89
    {
        prev++;//8+1=10

        // If we reached next block or end of
        // array, element is not present.
        if (prev == min(step, n))//step==12 
            return -1;
    }
    
    
    
    if (arr[prev] == x)
        return prev;

        
        
        
        //
    return -1;
}

// Driver program to test function
int main()
{
    int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
                34, 55, 89, 144, 233, 377, 610 };
    int x = 55;
    int n = sizeof(arr) / sizeof(arr[0]);

    cout<<"the size of array "<<n<<endl;//16

    // Find the index of 'x' using Jump Search
    int index = jumpSearch(arr, x, n);

    // Print the index where 'x' is located
    cout << "\nNumber " << x << " is at index " << index;
    return 0;
}

4.interpolationSerach.cpp

// C++ program to implement interpolation search
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
int interpolationSearch(int arr[], int n, int x)//x=18
{
    // Find indexes of two corners
    int lo = 0, hi = (n - 1);//14

    // Since array is sorted, an element present
    // in array must be in range defined by corner
    while (lo <= hi && x >= arr[lo] && x <= arr[hi])
    {
        if (lo == hi)//lo=4
        {
            if (arr[lo] == x) return lo;
            return -1;
        }
        // Probing the position with keeping // 0.378 // 3.0
        // uniform distribution in mind. 14             //37
        int pos = lo + (((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));//3

        // Condition of target found
        if (arr[pos] == x)
            return pos;

        // If x is larger, x is in upper part
        if (arr[pos] < x)
            lo = pos + 1;//4

        // If x is smaller, x is in the lower part
        else
            hi = pos - 1;
    }
    return -1;
}

// Driver Code
int main()
{
    // Array of items on which search will
    // be conducted.
    int arr[] = {10, 12, 13, 16, 18, 19, 20, 21,
                 22, 23, 24, 33, 35, 42, 47};//15
    int n = sizeof(arr)/sizeof(arr[0]);

    int x = 18; // Element to be searched
    int index = interpolationSearch(arr, n, x);

    // If element was found
    if (index != -1)
        cout << "Element found at index " << index;
    else
        cout << "Element not found.";
    return 0;
}

// This code is contributed by Mukul Singh.