Searching in Arrays:
====================
Defination:
------------
--Searching is the process of finding the position (index) of a particular element
(called the target) in a given array or list.
Types of Searching:
--------------------
--We can search for an element in an array using 3 common techniques:
1. Linear Search
2. Binary Search (Only for sorted arrays)
3. Hashing-based Search (Using hash tables/maps)
1. Linear Search
-----------------
Logic:
--Traverse the array from left to right.
--Compare each element with the target.
--Return the index as soon as a match is found.
--If no match is found, return -1.
Note: If duplicates exist, it returns the first occurrence.
Example:
int linearSearch(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target)
return i;
}
return -1;
}
Time Complexity:
Worst Case: O(n)
Best Case: O(1) (if the element is at the beginning)
Divide and conquer strategy:
---------------------------
--It is a strategy to solve a problem. It is a one kind of approach or desing to
solve a problem.
--if a problem p of some size(input) n is given, and if we say the problem p is
large, then we can divide this large problem into smaller sub problems (p1, p2,
p3,...pk) as many as sub problems.
--Now solve these sub problems individually (often recursively) and obtains their
solution. (If the sub problem is still large then divide it again into the another
sub problems)
--once we have the solution of all the sub problems individually, then we can
combine(merge) all the solutions to get the solution of the main problem.
Step-by-Step Process:
---------------------
1. Divide the problem into smaller sub-problems.
2. Conquer each sub-problem by solving it recursively. If a sub-problem is still
too large, divide it again.
3. Combine the solutions of the sub-problems to form the final answer.
Important rule:
----------------
1. Sub-problems must be of the same type as the original problem.
For example:
If the main problem is sorting, sub-problems must also be sorting tasks.
If the main problem is searching, sub-problems must also involve searching.
--Non-similar sub-tasks are not considered divide and conquer.
Example: Organizing a workshop (making posters, inviting guests) – these are
unrelated tasks.
2. You must have a way to combine the solutions of the sub-problems into the
solution of the main problem.
--If you can't combine the solutions, this strategy won't work.
3. Divide and Conquer is recursive in nature.
Common problems to solve using divide and conquer:
--------------------------------------------------
1. Binary search
2. Find Min and Max in Array
3. merge sort
4. quick sort
5. Matrix Multiplication
..
2. Binary Search
-----------------
Logic:
--Binary Search is used on sorted arrays (ascending or descending).
--It works by repeatedly dividing the search range in half.
--the time complexity of the binary search will be less than O(n) ?
Note: the binary search algorithm is based on divide and conquer strategy.
Example:
vector<int> arr={1,3,4,7,9,11,14,16,19,21,23,27,31,45};
int target = 16;
int n=arr.size(); //14
here we need to take 3 pointers:
1. low: points to the begining index: 0
2. high: points to the last (n-1) index => arr.size()-1 => 14-1: 13th index
3. mid: points to the middle index (low+high)/2 => (0+13)/2 => 6th index
--since we already know that the given array is sorted,
so,
Case1: if the mid index element matches with the target element then simply returns
it.
Case2: if the mid index element is less than the target element then we no need to
search the left side of the mid index element. i.e(element should be there at right
side)
Case3: if the mid index element is greater than target element then we no need to
search the right side of the mid index element. i.e(element should be there at left
side)
therefore:
in Case2: arr[mid] < target, just change the low = mid+1;
in Case3: arr[mid] > target, just change the high = mid-1;
Rules:
If arr[mid] == target → return index
If arr[mid] < target → search right side: low = mid + 1;
If arr[mid] > target → search left side: high = mid - 1;
vector<int> arr={1,3,4,7,9,11,14,16,19,21,23,27,31,45};
int target = 16;
Here at the first iteration the total elements will be there in the search case: n
and at the second iteration the total elements will be there in the search case:
n/2
like that with each iteration the search elements will be halved.
Explaination:
-------------
vector<int> arr = {1,3,4,7,9,11,14,16,19,21,23,27,31,45};
int target = 16;
We need 3 pointers:
1. low = 0 (start of array)
2. high = arr.size()-1 = 13 (end of array)
3. mid = (low + high) / 2 = (0+13)/2 = 6
arr[mid] = arr[6] = 14
Since arr[mid] < target,
→ The element must be in the right half (greater side)
→ So we update: low = mid + 1 = 7
Next iteration:
low = 7, high = 13
mid = (7 + 13)/2 = 10
arr[10] = 23
Since arr[mid] > target,
→ The element must be in the left half
→ So we update: high = mid - 1 = 9
Next:
low = 7, high = 9
mid = 8 → arr[8] = 19 → still > target → high = 7
Now:
low = 7, high = 7
mid = 7 → arr[7] = 16 : match found!
Code:
-----
int binarySearch(vector<int> arr, int target){
int low=0;
int high= arr.size()-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;
Note: to avoid the integer overflow problem when low and high are large values
(low+high can exceed INT_MAX).
we can use the following formula to calculate the mid value:
int mid = low+(high-low)/2;
calculating the TC of the above binary search code:
---------------------------------------------------
At iteration 1: elements left = n
At iteration 2: elements left = n / 2
At iteration 3: elements left = n / (2 × 2) => n / 2^2
At iteration 4: elements left = n / (2 × 2 × 2) => n / 2^3
...
At iteration k: elements left = n / (2 × 2 × ... × 2) (k times)
= n / (2 × 2 × ... × 2) => n / (2ᵏ)
The loop stops when only 1 element is left:
=n / (2ᵏ) = 1
= 2ᵏ = n
k = O(log n) (base 2)
The number of iterations in binary search = log base 2 of n
Space Complexity: O(1)
Note: If the sorted array has the duplicate elements it can return any matching
element index based on the mid value calculation.
example:
---------
vector<int> arr = {1, 3, 3, 3, 5, 7, 9}; // Sorted with duplicates
int target = 3;
--it can return index 2 or 1 or 3 based on the mid value calculation
example:
vector<int> arr = {1, 2, 3, 3, 3, 4, 5};
int target= 3;
if we want the first occurrence:
---------------------------------
int firstOccurrence(vector<int>& arr, int target) {
int result= -1;
int low = 0;
int high = arr.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
high = mid - 1; // keep searching left
} else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return result;
}
Last occurrence of a target:
-----------------------------
int lastOccurrence(vector<int>& arr, int target) {
int result= -1;
int low = 0;
int high = arr.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
low = mid + 1; // keep searching right
} else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return result;
}
Counting the number of occurance of duplicate elements using binary search:
===========================================================================
To count the number of duplicate occurrences of a target element in a sorted array,
you can use binary search to find:
x= The first occurrence index of the target.
y = The last occurrence index of the target.
count = y - x + 1
safe side:
if(x == -1 && y == -1){
return 0;
}else{
return count;
}
or we can merge both function in only (first occurrence of the target function)
int findOccurrence(vector<int>& arr, int target, bool findFirst) {
int low = 0, high = arr.size() - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
if (findFirst)
high = mid - 1; // move left
else
low = mid + 1; // move right
} else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return result;
}
int countOccurrences(vector<int>& arr, int target) {
int first = findOccurrence(arr, target, true);
int last = findOccurrence(arr, target, false);
return last - first + 1;
}
Q/- Find the floor of the square root of a number without using built-in functions.
floor of the square root means:
--get the square root of a number
--then ignore the decimal part, that integer will become the floor number.
example:
sqrt(10) = 3.16 → floor = 3
sqrt(25) = 5 → floor = 5
sqrt(30) = 5.47 → floor = 5
using brute force:
------------------
Logic:
Try all numbers starting from 1, and check i*i until it exceeds n. When i * i > n
stop and, the answer is i - 1.
For n = 10, this will:
i = 1 → 1
i = 2 → 4
i = 3 → 9
i = 4 → 16 → stop
Return 4 - 1 = 3.
code:
------
int floorSquareRoot(int num){
int i=1;
while((long long) i * i <= num){
i++;
}
return i-1;
Here TC: O(√n) – because the loop runs until i*i > num.
if the n=625, then it will take 25 iteration.
using binary search approach:
------------------------------
--Using binary search to reduce the number of checks.
low =1;
high = n
mid= low+(high-low)/2 ==> 313
lets compute mid*mid, if it is grater than n then
high = mid-1 ==> 312
now new mid value will be 156
156*156 will be bigger than n
high = mid-1 ==> 155
now new mid value will be 78
78*78 will be bigger than n
high = mid-1 = 77
until mid*mid <= 625
almost 9 to 10 iteration.
example
int floorSquareRoot(int n){
int low = 1;
int high = n;
int result=-1;
while(low <=high){
int mid = low+(high-low)/2;
if((long long) mid*mid <= n){
result = mid; // Store possible answer
low = mid+1; // Try to find a larger one
}else
high= mid-1; // Go to the smaller half
return result;
}
TC: O(log n)
SC: O(1)
Q/- Find the minimum element in a rotated sorted array.
--A rotated sorted array consists of two sorted subarrays.
--The pivot point (drop from higher to lower) is where the minimum element lies.
Example:
arr= {2,3,4,5,6,7,8,9,10}
left rotated by 3 (pivot point)
[5, 6, 7, 8, 9, 10, 2, 3, 4]
1st sorted array: [5,6,7,8,9,10]
2nd sorted array: [2,3,4]
But overall:
[10 → 2] is a point where order drops(rotation point). and that drop leads to the
minimum.
--We will try to find where the drop occurs — the point where arr[i] > arr[i+1].
code:
------
int findMin(vector<int>& arr) {
int low = 0;
int high = arr.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) {
// Drop is on the right side
low = mid + 1;
} else {
// Could be mid or in the left side
high = mid;
}
}
return arr[low];
}
Because if the whole array were sorted, we should have:
arr[mid] < arr[high] if no drop.
So when arr[mid] > arr[high], the drop must be on the right side, meaning:
the right half is unsorted in the global view, and that’s where the minimum is.
recursion:
=========
--Recursion means a function calling itself to solve smaller versions of the same
problem.
Structure of a Recursive Function:
void function() {
// 1. Base Case (stopping condition)
if (condition) return;
// 2. Recursive Case (function calls itself)
function();
}
Important Terms:
1. Base Case → When to stop calling the function.
2. Recursive Case → When the function calls itself with a smaller/simpler input.
Example:
void fun(int num){
if(num == 0)
return;
cout<<num <<" ";
fun(num-1);
output: 5,4,3,2,1
Example:2
void fun(int num){
if(num == 0)
return;
fun(num-1);
cout<<num <<" ";
gues the output:
Binary serach using recursion:
------------------------------
Idea:
------
At each step:
1. Find the middle of the array.
2. If middle element == key → return index
3. If key < middle → search in left half
4. If key > middle → search in right half
code:
-----
int binarySearch(vector<int>& arr, int low, int high, int key) {
if (low > high)
return -1; // Base Case: Not found
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid; // Found
else if (key < arr[mid])
return binarySearch(arr, low, mid - 1, key); // Search left half
else
return binarySearch(arr, mid + 1, high, key); // Search right half
}
int main(){
vector<int> arr = {2, 4, 6, 8, 10, 12, 14};
int key = 10;
int index = binarySearch(arr, 0, arr.size()-1, key);
cout<<"Index is: "<<index;
return 0;
Task:
------
Using recursion find out:
1. factorial of a number
2. Sum of First N Natural Numbers
3. Find the nth Fibonacci number using recursion.
Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13...
4. find out the power of a number
Find a^b using recursion.
