Example:
START
FOR each element in array
IF element == target
RETURN position
END FOR
RETURN -1
STOP
Step-by-Step Explanation
1. START
The algorithm begins execution.
2. FOR each element in array
The algorithm checks every element one by one in the array.
Example array:
[10, 25, 30, 45]
3. IF element == target
It compares the current element with the target value.
Example:
target = 30
Comparisons:
10 == 30 → No
25 == 30 → No
30 == 30 → Yes
4. RETURN position
If the target is found, the algorithm returns its index/position.
Example:
30 is at position 2
(Positions usually start from 0.)
5. END FOR
If not found yet, continue checking remaining elements.
6. RETURN -1
If the loop finishes and the target is not found, return -1.
-1 means:
Target does not exist in array
7. STOP
Algorithm ends.
Example
Array:
[5, 8, 12, 20]
Target:
12
Process:
Check 5 → not equal
Check 8 → not equal
Check 12 → found
Output:
Position = 2
Time Complexity
For Linear Search:
Best Case: O(1)
(target found at first element)
Worst Case: O(n)
(target found at last element or not found)
Real-Life Example
Searching for a name in a handwritten attendance list:
Start from top
Check each name one by one
Stop when the required name is found
Python Code:
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
Line-by-Line Explanation
1. Function Definition
def linear_search(arr, target):
def → used to define a function in Python
linear_search → function name
arr → list/array to search in
target → value to find
Example call:
linear_search([10, 20, 30], 20)
2. Loop Through Array
for i in range(len(arr)):
Explanation:
len(arr) gives total number of elements
range(len(arr)) generates indexes
i stores current index
Example:
arr = [10, 20, 30]
Then:
range(len(arr)) → range(3)
Indexes become:
0, 1, 2
3. Compare Element with Target
if arr[i] == target:
Checks whether current element equals target value.
Example:
arr[i] = 20
target = 20
Condition becomes:
20 == 20
Which is True.
4. Return Index
return i
If target is found:
function immediately returns its position/index
Example:
arr = [10, 20, 30]
target = 20
Output:
because 20 is at index 1.
5. Target Not Found
return -1
If loop finishes without finding target:
return -1
Meaning:
Element does not exist in array
Complete Example
Code
arr = [5, 8, 12, 20]
result = linear_search(arr, 12)
print(result)
Execution Steps
arr[ Compare with
i
i] 12
05 No
18 No
arr[ Compare with
i
i] 12
2 12 Yes
Returns:
Output
If Element Not Found
Code
arr = [5, 8, 12, 20]
result = linear_search(arr, 50)
print(result)
Output
-1
Time Complexity
Linear Search Complexity:
Best Case → O(1)
Worst Case → O(n)
where n = number of elements.
Simple Summary
This function:
1. Checks each element one by one
2. Compares it with target
3. Returns index if found
4. Returns -1 if not found
Pseudocode
SET low = 0, high = n-1
WHILE low <= high
mid = (low + high) / 2
IF arr[mid] == target
RETURN mid
ELSE IF arr[mid] < target
low = mid + 1
ELSE
high = mid - 1
RETURN -1
Step-by-Step Explanation
1. Initialize Variables
SET low = 0, high = n-1
low → first index
high → last index
n → total number of elements
Example:
arr = [2, 5, 8, 12, 16, 20]
Indexes:
0 1 2 3 4 5
So:
low = 0
high = 5
2. Repeat Until Search Space Ends
WHILE low <= high
Continue searching while valid range exists.
3. Find Middle Element
mid = (low + high) / 2
This calculates middle index.
Example:
low = 0
high = 5
mid = (0 + 5)/2 = 2
4. Check Middle Element
IF arr[mid] == target
If middle element equals target:
RETURN mid
Search successful.
5. Search Right Half
ELSE IF arr[mid] < target
low = mid + 1
If middle value is smaller than target:
ignore left half
search in right half
Example:
arr[mid] = 8
target = 16
Since:
8 < 16
move right:
low = mid + 1
6. Search Left Half
ELSE
high = mid - 1
If middle value is greater than target:
ignore right half
search in left half
7. Element Not Found
RETURN -1
If loop finishes:
target does not exist
Complete Example
Array:
[2, 5, 8, 12, 16, 20]
Target:
16
Iteration 1
low = 0
high = 5
mid = 2
arr[mid] = 8
Since:
8 < 16
Move right:
low = 3
Iteration 2
low = 3
high = 5
mid = 4
arr[mid] = 16
Found target.
Return:
Time Complexity
Binary Search Complexity:
Best Case → O(1)
Worst Case → O(log n)
Much faster than Linear Search for large arrays.
Binary Search vs Linear Search
Linear Binary
Feature
Search Search
Array must be
No Yes
sorted
Worst Time
O(n) O(log n)
Complexity
Divide into
Searching Method One by one
halves
#include <iostream>
using namespace std;
// Function for Linear Search
int linear_search(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Return index if target found
return -1; // Return -1 if target not found
int main() {
int arr[] = {5, 8, 12, 20};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 12;
int result = linear_search(arr, size, target);
if (result != -1) {
cout << "Element found at index: " << result << endl;
} else {
cout << "Element not found" << endl;
return 0;}
Explanation
Function Definition
int linear_search(int arr[], int size, int target)
arr[] → array to search
size → total elements in array
target → value to find
Loop Through Array
for (int i = 0; i < size; i++)
Checks each element one by one.
Compare Element
if (arr[i] == target)
If current element equals target:
return i;
returns its index.
If Not Found
return -1;
means target does not exist in array.
Example Output
Element found at index: 2
Code
int binarySearch(int arr[], int n, int target){
int low = 0, high = n-1;
while(low <= high){
int mid = (low + high)/2;
if(arr[mid] == target)
return mid;
else if(arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
Step-by-Step Explanation
1. Function Definition
int binarySearch(int arr[], int n, int target)
Parameters:
arr[] → sorted array
n → size of array
target → element to search
Return:
index of target if found
-1 if not found
2. Initialize Low and High
int low = 0, high = n-1;
low → first index
high → last index
Example:
Array = [2, 5, 8, 12, 16, 20]
Indexes = 0 1 2 3 4 5
Initially:
low = 0
high = 5
3. Loop Until Search Ends
while(low <= high)
Continue searching while valid range exists.
4. Find Middle Index
int mid = (low + high)/2;
Calculates middle position.
Example:
low = 0
high = 5
mid = 2
5. Check If Element Found
if(arr[mid] == target)
return mid;
If middle element equals target:
return its index immediately
Example:
arr[mid] = 12
target = 12
Returns:
3
6. Search Right Half
else if(arr[mid] < target)
low = mid + 1;
If middle value is smaller:
target must be on right side
Move:
low = mid + 1
7. Search Left Half
else
high = mid - 1;
If middle value is greater:
target must be on left side
Move:
high = mid - 1
8. Target Not Found
return -1;
If loop finishes:
target does not exist in array
Example Execution
Array:
[2, 5, 8, 12, 16, 20]
Target:
16
Iteration 1
low = 0
high = 5
mid = 2
arr[mid] = 8
Since:
8 < 16
Move right:
low = 3
Iteration 2
low = 3
high = 5
mid = 4
arr[mid] = 16
Target found.
Return:
Time Complexity
Binary Search is very efficient.
Complexity
Best Case → O(1)
Worst Case → O(log n)
Important Note
Binary Search only works correctly if array is:
SORTED
Example:
[1, 3, 5, 7, 9]
Not:
[7, 2, 9, 1]