Basic DSA programs in c++
1. Linear Search
#include <iostream>
using namespace std;
int linearSearch(int arr[], int size, int key) {
for (int i = 0; i
< size; i++) {
if (arr[i] ==
key)
return i;
// Return index if found
}
return -1; //
Return -1 if not found
}
int main() {
int arr[] = {10,
20, 30, 40, 50};
int size =
sizeof(arr) / sizeof(arr[0]);
int key;
cout <<
"Enter the element to search: ";
cin >> key;
int result =
linearSearch(arr, size, key);
if (result != -1)
cout <<
"Element found at index " << result << endl;
else
cout <<
"Element not found." << endl;
return 0;
}
Explanation of Linear Search in C++
Linear Search is the simplest searching algorithm that sequentially
checks each element of an array until the target element (key) is found.
Breakdown of the C++ Code
1. Function: linearSearch
int linearSearch(int arr[], int size, int key) {
for (int i = 0; i
< size; i++) { // Loop through each
element
if (arr[i] ==
key) // If element matches key
return
i; // Return index of the
element
}
return -1; // If
element is not found, return -1
}
- This
function takes an array (arr[]), its size (size), and the element
to search (key).
- It iterates
through the array and compares each element with key.
- If
found, it returns the index; otherwise, it returns -1.
2. Main Function:
int main() {
int arr[] = {10,
20, 30, 40, 50}; // Array declaration
int size =
sizeof(arr) / sizeof(arr[0]); // Calculate array size
int key;
cout <<
"Enter the element to search: ";
cin >>
key; // Take input for the key to search
int result =
linearSearch(arr, size, key); // Call linearSearch function
if (result !=
-1) // If element is found
cout <<
"Element found at index " << result << endl;
else
cout <<
"Element not found." << endl;
return 0;
}
- The
user enters a number (key) to search in the array.
- The
linearSearch function is called with the array, its size, and the key.
- If
the function returns an index (found case), it prints the index.
- If
it returns -1 (not found), it prints "Element not found."
Example Execution
Input:
Enter the element to search: 30
Process:
- linearSearch
checks arr[0] = 10 → Not a match
- linearSearch
checks arr[1] = 20 → Not a match
- linearSearch
checks arr[2] = 30 → Match found at index 2
Output:
Element found at index 2
Time Complexity Analysis
|
Case |
Complexity |
|
Best Case (First element is the key) |
O(1) |
|
Average Case |
O(n/2) → O(n) |
|
Worst Case (Last element or not found) |
O(n) |
- Best
Case: The element is found at the first position.
- Worst
Case: The element is not in the array, or it's at the last
position.
Space Complexity
- O(1)
→ Only a few variables are used, no extra space is required.
When to Use Linear Search?
✅ Advantages:
- Works
on unsorted and sorted arrays.
- Simple
to implement.
❌ Disadvantages:
- Slow
for large datasets (O(n) complexity).
- Not
efficient compared to binary search.
🔹 For large sorted
arrays, use Binary Search (O(log n)) instead of Linear Search.
Would you like an explanation of Binary Search next? 🚀
2. Binary Search (Array must be sorted)
#include <iostream>
using namespace std;
int binarySearch(int arr[], int size, int key) {
int low = 0, high
= size - 1;
while (low <=
high) {
int mid = low
+ (high - low) / 2;
if (arr[mid]
== key)
return
mid;
else if
(arr[mid] < key)
low = mid
+ 1;
else
high = mid
- 1;
}
return -1; //
Element not found
}
int main() {
int arr[] = {10,
20, 30, 40, 50};
int size =
sizeof(arr) / sizeof(arr[0]);
int key;
cout <<
"Enter the element to search: ";
cin >> key;
int result =
binarySearch(arr, size, key);
if (result != -1)
cout <<
"Element found at index " << result << endl;
else
cout <<
"Element not found." << endl;
return 0;
}
3. Bubble Sort
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int size) {
for (int i = 0; i
< size - 1; i++) {
for (int j =
0; j < size - i - 1; j++) {
if (arr[j]
> arr[j + 1]) {
//
Swap
int
temp = arr[j];
arr[j]
= arr[j + 1];
arr[j
+ 1] = temp;
}
}
}
}
int main() {
int arr[] = {64,
34, 25, 12, 22, 11, 90};
int size =
sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr,
size);
cout <<
"Sorted array: ";
for (int i = 0; i
< size; i++) {
cout <<
arr[i] << " ";
}
cout <<
endl;
return 0;
}
4. Stack Implementation Using Arrays
#include <iostream>
#define MAX 100
using namespace std;
class Stack {
private:
int arr[MAX];
int top;
public:
Stack() { top =
-1; }
void push(int x) {
if (top >=
MAX - 1) {
cout
<< "Stack Overflow" << endl;
return;
}
arr[++top] =
x;
}
void pop() {
if (top <
0) {
cout
<< "Stack Underflow" << endl;
return;
}
top--;
}
int peek() {
if (top <
0) {
cout
<< "Stack is empty" << endl;
return -1;
}
return
arr[top];
}
bool isEmpty() {
return top
< 0;
}
};
int main() {
Stack s;
s.push(10);
s.push(20);
s.push(30);
cout <<
"Top element is: " << s.peek() << endl;
s.pop();
cout <<
"Top element after pop is: " << s.peek() << endl;
return 0;
}
5. Queue Implementation Using Arrays
#include <iostream>
#define MAX 100
using namespace std;
class Queue {
private:
int arr[MAX];
int front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
void enqueue(int
x) {
if (rear ==
MAX - 1) {
cout
<< "Queue Overflow" << endl;
return;
}
if (front ==
-1)
front = 0;
arr[++rear] =
x;
}
void dequeue() {
if (front ==
-1 || front > rear) {
cout
<< "Queue Underflow" << endl;
return;
}
front++;
}
int peek() {
if (front ==
-1 || front > rear) {
cout
<< "Queue is empty" << endl;
return -1;
}
return
arr[front];
}
bool isEmpty() {
return front
== -1 || front > rear;
}
};
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
cout <<
"Front element is: " << q.peek() << endl;
q.dequeue();
cout <<
"Front element after dequeue is: " << q.peek() << endl;
return 0;
}
Comments
Post a Comment