Data Structure and Algorithms based on the Object-oriented programming
(OOP) where some are the base of OOP for an instant inheritance,
polymorphism, Encapsulation, and Abstraction, etc. Now we will start learning
data structures in programming languages such as Linked list, arrays, Structs,
Classes, Queues, Stacks, etc.
Today’s Concept:
Linear & Binary Data Structure
Prerequisite of
this Lab is all those students who have basic concepts on C++ Programming such
as Syntax of Language, the concept of functions, pointers, data types, etc. Visual
Studio 2012 and onward version will be used for implementation and programming
tasks assigned in the Lab.
Linear search scans whole items
in the array one by one and camper with the key element which user enter for
search this is the simple data structure used for searching in arrays with the
time complexity O(n).
Implementation of Linear Search
in C++:
#include <iostream>
using namespace std;
void search(int arr[], int n, int x)
{
int
i;
for
(i = 0; i < n; i++)
{
if
(arr[i] == x)
{
cout<<"Element is searched
and present in the array"<<endl;
break;
}
}
}
int main(void)
{
int
arr[] = { 2, 3, 4, 10, 40 };
int
x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
search(arr, n, x);
return 0;
}
Binary
Search is the Data Structure used to search elements in the arrays, but it
needs an already sorted array to implement Binary Search. It searches for an element
with the time complexity O(log(n)) because it always half the search space.
#include <iostream>
using namespace std;
bool binarySearch(int array[],int size, int key);
int binarySearch(int arr[], int l, int r, int x)
{
if
(r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr,
mid + 1, r, x);
}
return -1;
}
int main(void)
{
int
arr[] = { 2, 3, 4, 10, 40 };
int
x = 10;
int
n = sizeof(arr) / sizeof(arr[0]);
int
result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not
present in array"
: cout << "Element is present at
index "
<< result;
return 0;
}
bool binarySearch(int array[],int size, int key){
int
start=1, end=size;
int
mid=(start+end)/2;
while(start<=end&&array[mid]!=key){
if(array[mid]<key){
start=mid+1;
}
else{
end=mid-1;
}
mid=(start+end)/2;
}// While Loop End
if(array[mid]==key)
return true; //Returnig to main
else
return false;//Returnig to main
cout<<"\n\n\n";
}//
binarySearch Function Ends Here
Post a Comment