PRACTICAL NO.

03
Binary Search Algorithm
PLO CLO LL
OBJECTIVE:
Understand and implementing the concept of binary search algorithm iteratively. Demonstrate
how to apply binary search to search for an element in a sorted array. Discuss the limitations
of binary search. Illustrate the step-by-step process of binary search with examples. Implement
binary search in a practical programming problem or application.

Theory Overview
Binary search is an efficient algorithm for finding a target value within a sorted array. It works
by repeatedly dividing the search interval in half. If the value of the target is less than the
middle element of the interval, the search continues in the lower half. If the value is greater,
the search continues in the upper half. This process is repeated until the target value is found
or the interval is empty.
Iterative Approach
1. Elements in array must be sorted.
2. Divide the array into two parts.
3. Use variables mid, start and end.
4. Where start = 0 and end = no of elements – 1.
5. For searching use while loop.
6. Set the value of mid = start + end / 2.
7. Compare the element on mid index with target value.
8. If matched display found else compare it with the element present on start and end
index.
9. If the element on mid index is smaller than target value than start = mid + 1.
10. If the element on mid index is greater than target value than end = mid - 1.
11. Repeat step 6-10 until the match is found.

Time Complexity
Binary search has a time complexity of O(log n), where n is the number of elements in the
array. This makes it significantly more efficient than linear search (O(n)), especially for large
arrays.

Applications
Binary search is commonly used in scenarios where the data is sorted and efficient searching
is required. It is used in various applications such as searching in databases, finding elements
in sorted arrays, and more.

Limitations
Binary search requires the array to be sorted, which can add an additional overhead if the array
is frequently modified.
It may not be suitable for small arrays or unsorted data, as the overhead of sorting or
maintaining a sorted array may outweigh the benefits of binary search.
Comparisons
Linear Search: Binary search is more efficient than linear search for large arrays, as it has a
lower time complexity.
Conclusion
Binary search is a powerful algorithm for efficiently finding elements in a sorted array.
Understanding its implementation and limitations can help in applying it effectively to various
problem-solving scenarios.

TASK 1:
Design a game that asks the user to guess a no within a specific range and then the program
will guess that number :(Hint! Use Binary search)

TASK 2:

You are working on a project to develop a simple phone book application. The application
stores contact information such as name, phone number and address. You decide to implement
a search feature using the binary search algorithm to efficiently find contact information based
on the name.
Question: Given an array of contacts sorted alphabetically by name, write a function in C++ to
perform a binary search to find the contact information for a given name. Define the structure/
class for a contact that includes the name and phone number. Also, discuss the time complexity
of the binary search algorithm in this scenario.

TASK 3:
You are developing a video game where players can collect items throughout the game. Each
item has a unique name and a rarity level (common, rare, epic, legendary). The game allows
players to search for items in their collection. Sort out the array based on their rarity level.
To improve the search functionality, you decide to implement a binary search algorithm to
quickly find items based on their names. The items are sorted alphabetically by name to
facilitate the binary search process.
Delete the record of searched player and display the record of remaining players.

CONCLUSION:
___________________________________________________________________________
___________________________________________________________________________
__________________________________________________________________________
RUBRICS:

Performance Lab Report

Description Total Marks Description Total Marks

Marks Obtained Marks Obtained
Ability to 5 5
Conduct Structure
practical
5 5
Data Analysis &
Efficiency
Interpretation
Total Marks obtained Total Marks Obtained
PRACTICAL NO.04

PLO CLO LL
OBJECTIVE:
Understand the applications of stacks.
Implement stacks using both static and dynamic implementation.
Theory Overview
Stack is a memory portion, which is used for storing the elements. The elements are stored
based on the principle of LIFO (Last In, First Out). In stack insertion and deletion of elements
take place at the same end (Top). The last element inserted will be the first to be retrieved.
• This end is called Top
• The other end is called Bottom

Top: The stack top operation gets the data from the top-most position and returns it to the user
without deleting it. The underflow state can also occur in stack top operation if stack is empty.
Push: The push operation adds a new element to the top of the stack or initializes the stack if it
is empty. If the stack is full and does not contain enough space to accept the given item, the
stack is then considered to be in an overflow state.
Pop: The pop operation removes an item from the top of the stack. A pop either returns
previously inserted items, or NULL if stack is empty.
Underflow: When stack contains equal number of elements as per its capacity and no more
elements can be added, the status of stack is known as overflow.
Stacks can be implemented using arrays or linked lists.
Arrays are simpler but have a fixed size, while linked lists can grow dynamically but require
more memory per element.
#include<iostream>
using namespace std;
const int n = 5;
int Stk[n];
int top = -1;
void push()
{
int num;
cout<<"enter the number you want to insert"<<endl;
cin>>num;
if(top == n-1)
{
cout<<"Overflow"<<endl;
}
else
{
top++;
Stk[top] = num;
}
}
void pop()
{
int ele;
if(top == -1)
{
cout<<"underflow"<<endl;
}
else
{
ele = Stk[top];
top--;
cout<<"the deleted element is :"<<ele<<endl;
}
}
void peek()
{
if(top == -1)
{
cout<<"stack is empty"<<endl;
}
else
{
cout<<Stk[top]<<endl;
}
}
void isempty()
{
if(top== -1)
{
cout<<"stack is empty"<<endl;
}
else
{
cout<<"stack is not empty"<<endl;
}
}
void display()
{
for(int i = top; i>=0; i--)
{
cout<<Stk[i]<<" ";
}
}

int main()
{
push();
push();
push();
push();
push();
push();
pop();
peek();
isempty();
display();
return 0;
}

Stack implementation using STL

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

// Push elements onto the stack

myStack.push(1);
myStack.push(2);
myStack.push(3);

// Print the top element of the stack

cout << "Top element: " << myStack.top() << endl;

// Pop elements from the stack

myStack.pop();

// Check if the stack is empty

if (myStack.empty()) {
cout << "Stack is empty." << endl;
} else {
cout << "Stack is not empty." << endl;
}

return 0;
}
Time Complexity
The time complexity of push, pop, peek, isEmpty, and size operations is O(1) for both array
and linked list implementations.

Task 1
Write a program using stack operations, which accepts a non-negative base 10 integer as a
parameter, and display binary representation of number.
Description: To convert a number from decimal to binary, you simply divide by two and push
reminder to stack until quotient is reached to zero, then use pop operation to display the binary
representation of number. For example, to convert (35)10 to binary, you perform the following
computation.
35/2 = 1
17/2 = 1
8/2 = 0
4/2 = 0
2/2 = 0
1
If you examine the remainders from the last division to the first one, writing them down as you
go, you will get the following sequence: 100011. i.e. (100011)2 = (35)10

Task 2
Write a program to compare opening and closing brackets in expression. This program takes
an expression in the form of string and scan it character by character. Finally, the output of the
program is the valid or invalid expression.
Algorithm: To do this comparison a stack ADT can be used to keep track of the scope delimiters
encountered while scanning the expression.
Whenever a scope < opener = is encountered, it can be < pushed = onto a stack.
Whenever a scope < ender = is encountered the stack is examined:
➢ If the stack is <empty =, there is no matching scope <opener= and the expression is
invalid.
➢ If the stack is not empty, we pop the stack and check if the <popped = item corresponds
to the scope ender.
➢ If match occurs, we continue scanning the expression.
When end of the expression string is reached, the stack must be empty, otherwise one or more
opened scopes have not been closed and the expression is invalid.

Infix to Postfix:
An algorithm for parsing an infix notation without parentheses is given here.
Algorithm:
➢ Create an empty stack called opstack for keeping operators.
➢ Create an empty string for output. Each character in string is a token.
➢ Scan the token list from left to right. o If the token is an operand, append it to the end
of the output string. o If the token is a left parenthesis, push it on the opstack.
➢ If the token is a right parenthesis, pop the opstack until the corresponding left
parenthesis is removed.
➢ Append each operator to the end of the output string.
➢ If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove
any operators already on the opstack that have higher or equal precedence and append
them to the output list.
When the input expression has been completely processed, check the opstack. Any operators
still on the stack can be removed and appended to the end of the output string.
Task 3:
Write c++ program to take a string expression as input from user. Using this infix expression,
you must convert it into its equivalent postfix notation.

Parsing Infix Notation:

An algorithm for parsing an infix notation without parentheses is given here. Two stacks are
required, one for numbers and the other for operators.
The algorithm is:
• For each item in the infix expression (no parentheses) from the right to the left o If the item
is a number then push it on the number stack. o If the item is an operator (+,-,*, or /) and: the
operator stack is empty or the operator on the top of the stack is higher in priority (* and / are
higher in priority than + or -), then
▪ Pop an operator from the operator stack.
▪ Pop two numbers off the number stack.
▪ Calculate using second number-operator-first number.
▪ Push the result on the number stack.
▪ Push the item on the operator stack. o Else push the item on the operator stack.
• After the loop, while the operator stack is not empty
➢ Pop an operator from the operator stack.
➢ Pop two numbers off the number stack.
➢ Calculate using second number-operator-first number.
➢ Push the result on the number stack.
The answer is the last item in the number stack.

Task 4:
Write a C++ code to evaluate the infix expression without parenthesis given by user:
CONCLUSION:
___________________________________________________________________________
___________________________________________________________________________
__________________________________________________________________________

RUBRICS:

Performance Lab Report

Description Total Marks Description Total Marks

Marks Obtained Marks Obtained
Ability to 5 5
Conduct Structure
practical
5 5
Data Analysis &
Efficiency
Interpretation
Total Marks obtained Total Marks Obtained