Brute Force Algorithm
A Brute Force algorithm is the simplest method to solve a problem.
It works by checking all possible solutions one by one until the correct solution is found.
It is also called:
Exhaustive Search
Generate and Test Method
Basic Idea
Instead of using smart tricks or optimizations, brute force:
1. Tries every possibility
2. Checks whether it satisfies the condition
3. Stops when the answer is found
Characteristics of Brute Force
1. Simple to Understand
Brute force algorithms are easy to write and understand.
2. Tries All Possibilities
Every possible solution is checked.
3. No Optimization
It does not use shortcuts or advanced logic.
4. Guaranteed Result
If a solution exists, brute force will find it.
Characteristics of Brute Force
1. Simple to Understand
Brute force algorithms are easy to write and understand.
2. Tries All Possibilities
Every possible solution is checked.
3. No Optimization
It does not use shortcuts or advanced logic.
4. Guaranteed Result
If a solution exists, brute force will find it.
Linear Search
Linear Search is a searching technique in which elements are searched sequentially one after another. It checks
each element one by one from the beginning until:
the element is found, or
the list ends.
It is also called Sequential Search
Working of Linear Search
Suppose we have an array:
[10, 20, 30, 40, 50]
We want to search for 30.
Steps:
1. Compare 30 with 10 → Not equal
2. Compare 30 with 20 → Not equal
3. Compare 30 with 30 → Found
Algorithm
1. Start from the first element
2. Compare each element with the target value
3. If matched → return position
4. If end of array reached → element not found
Binary Search
Binary Search is a fast searching algorithm used to find an element in a sorted array.
Instead of checking elements one by one like Linear Search, Binary Search repeatedly divides the array into
two halves.
It works on the principle of:
Divide and Conquer
Definition
Binary Search is a searching algorithm that finds an element in a sorted array by repeatedly dividing the search
interval into half.
Important Condition
Binary Search works only on:
Sorted arrays or lists
Example of sorted array:
[10, 20, 30, 40, 50]
Basic Idea
Suppose we want to search 40 in:
[10, 20, 30, 40, 50]
Step 1
Find middle element:
30
Compare:
40 > 30
So search in right half only.
Step 2
Right half:
[40, 50]
Middle = 40
Element found.
Working of Binary Search
Steps
1. Find middle element
2. Compare target with middle
3. If equal → found
4. If target smaller → search left half
5. If target greater → search right half
6. Repeat until found or interval becomes empty
Formula for Middle Index
mid=(low+high)/2
Where:
low = starting index
high = ending index
Search 70
Array:
[10, 20, 30, 40, 50, 60, 70, 80]
Step-by-Step
Step Low High Mid Value Result
1 0 7 3 40 Search right
2 4 7 5 60 Search right
3 6 7 6 70 Found
Backtracking:-
Backtracking is a problem-solving technique where we:
1. Choose one option
2. Explore further using recursion
3. If the choice becomes wrong, undo it
4. Try another option
It is called backtracking because the algorithm goes back (“tracks back”) after reaching a wrong path.
Main Idea of Backtracking
Backtracking works on:
1. Decision Making
Choose one possibility.
Example:
Place a queen on the chessboard
Choose a number
Move left/right in a maze
2. Recursion
After making a choice, solve the smaller remaining problem.
3. Undo (Backtrack)
If the choice does not work:
Remove the choice
Return to previous step
Try another option
Steps of Backtracking Algorithm
Step 1: Make a Choice
Choose one option from available choices.
Step 2: Check Validity
See whether the choice is valid.
Step 3: Move Forward
If valid, continue recursively.
Step 4: Backtrack
If solution fails:
Undo the choice
Try next option
How Backtracking Works
Suppose we want all permutations of:
[1, 2, 3]
Backtracking Tree
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] ...
The algorithm:
Picks one number
Continues recursively
Removes it after returning
Dry Run
Initial
path = []
used = [False, False, False]
Choose 1
path = [1]
Choose 2
path = [1, 2]
Choose 3
path = [1, 2, 3]
Complete permutation found.
Now backtrack:
Remove 3
Remove 2
Try another number