What is Data Structure?
        A data structure is a particular way of organizing data in a computer so that it can be used effectively.

Where Data Structures are used? 
       Data Structures can be used to organize, storage and retrieval of information stored  in both main memory and secondary memory.

What is Algorithm?
      Algorithm is set of instruction that is used to solve specific problem.an ideal algorithm must have less time and space complexity

Time complexity:
      It is used to describe the amount of time it takes to run/execute an algorithm. 

Space complexity:
        It is the memory required by an algorithm to execute a program and produce output.

Searching Algorithm: 

Linear Search-Program and Explanation

Binary Search-Program and Explanation  

Sentinel Linear Search-Program and Explanation  

Searching and Sorting:

1.Linear search-Algorithm and Program
2.Sentinel linear search-program and explanation
3.Binary search-Program with Example

Sentinel search | Sentinel Linear search explained with Program

Sentinel search or Sentinel Linear search is modified version of Linear search.Here the idea is to reduce the total number of comparison required to find element. This algorithm replace the last element of the array with the search element itself and run loop without checking index range of array because the element to be searched will definitely found at last position of array if search element is found then loop is terminated.

Program:
   while loop is used because sentinel search does not require to check index range of array.

#include

using namespace std;

int main()
{
    int arr[10],n,key,last;
    int no,i,j=0;
    cout<<"enter number of elements"<
    cin>>n;
    cout<<"enter the elements of array"<
    for(i=0;i
    {
        cin>>arr[i];
    }
    cout<<"enter number to be searched:";
    cin>>key;
    last=arr[n-1];
    arr[n-1]=key;
    while(arr[j]!=key)
    {
        j++;
    }
     arr[n-1]=last;
    if( (j
    {
        cout<
    }
    else
    {
        cout<<"number not found"<
    }
    
    return 0;

}

Output:

Linear search-Algorithm and Program of linear search

Linear search is also known as Sequential search.It is most popular and widely used searching algorithm.It does not require sorted array to search elements.

  Space complexity:  O(1)

  Time complexity:

Best case	Average case	Worst case
O(1)	O(n)	O(n)

Algorithm of linear search:

Step 1: Set i to 1 
Step 2: if i > n then go to step 7 
Step 3: if A[i] = x then go to step 6 
Step 4: Set i to i + 1 
Step 5: Go to Step 2 
Step 6: Print Element x Found at index i and go to step 8 
Step 7: Print element not found 
Step 8: Exit

Program of linear search:

#include<iostream>
 using namespace std;
   int main()

{
  int array[100], search, i, n;

  cout<<"Enter number of elements in array \n";
  cin>>n;

  cout<<"Enter integers \n";

  for (i=0; i<n; i++)
    cin>>array[i];

  cout<<"Enter a number to search \n";
    cin>>search;

  for (i=0; i<n; i++)
  {
    if (array[i] == search)    /* If required element is found */
    {
      cout<<"value is present at location:"<<i+1;
      break;
    }
  }
  if (i == n)
    cout<<" value isn't present in the array. \n";
  return 0;
}

Output:

Output of linear search

Binary Search-Pseudocode with Example and Program

    Binary search is most common and simple technique use to search specific number in array. Binary search requires sorted array  hence the complexity of binary search O(log n) is better than most of the searching algorithm.binary search first compare the search value with middle element of array if match found then program terminates.if search value is smaller than middle element then it will search that value in left part of array otherwise it will search that value in right part of array.

 Space complexity: O(1)

 Time complexity:

Best case	Average case	Worst case
O(1)	O(log n)	O(log n)

Example of  Binary search:
search element 20 from below array:

         10    20    30    40    50    60    70

here,

  start=0  and end=6 

  mid=(0+6)/2=3

  element at 3rd index(40) is middle element
  search element is 30
                        30 < 40
 now,
 start=0 and  end=mid-1=2
 mid=(start+end)/2=1
 element at 1st index is middle element
 thus search element 20 is found at 1st index position.

Pseudo-code:

  procedure binary_search
   A = sorted array
   n = size of array
   x = value to be searched
   Set first= 1
   Set last= n 

   while x not found
      if last < first 
      EXIT: x does not exists.
      set mid = first + last  / 2      
      if  x > A[mid]
         set first= mid + 1         
      
      if  x < A[mid]
         set last = mid - 1

      if A[mid] = x 
         EXIT: x found at location mid
   end while
end procedure


program of binary search:

#include <iostream>
using namespace std;
int main()
{
int n,arr[10];
cout<<"\n No. of elements ";
cin>>n;
cout<<"\Enter the elements in sorted order";
for(int i=0; i<n; i++)
{
cin>>arr[i];
}
int value, first, mid, last;
cout<<"\nEnter the value to search: ";
cin>>value;
first = 0;
last = n-1;
mid = (first+last)/2;
while(first<=last)
{
if(arr[mid]==value)
{
cout<<"\n value found at index "<<mid;
break;
}
else if(value < mid)
{
last = mid-1;
mid = (first+last)/2;
}
else if(value > mid)
{
first = mid+1;
mid = (first+last)/2;
}
}
if(first>last)
cout<<"\n value not found in the list";
return 0;
}

Output:

Output of binary search program