Binary Search (Recurrence Relation)

PUBLISHED: MAY 2, 2026•1 MIN READ

Binary SearchFloor Functionfloor(x): If x is a real number, then floor(x) is the greatest integer less than or equal to x.Ceil Functionceil(x): If x is a real n

Abhishek SinghAuthor

shellos

Binary Search

Floor Function

floor(x): If x is a real number, then floor(x) is the greatest integer less than or equal to x.

Ceil Function

ceil(x): If x is a real number, then ceil(x) is the smallest integer greater than or equal to x.

Binary Search Recursive Equation

Finding the middle element:

mid=\frac{low+high}{2}

Comparing the key with the middle element:
- If key == arr[mid] → element found
- If key < arr[mid] → search in left half
- If key > arr[mid] → search in right half

Recursive Equation

t(n)=C_1+C_2+t\left(\frac{n}{2}\right)

id
= Time to comparing key with mid
$t\left(\frac{2}\right)$ = Time to search in the remaining half the array

$dbyin

T(n)=T\left(\frac{n}{2^k}\right)+k

T(n)=T\left(\frac{n}{n}\right)+\log_2n

T(n)=1+log_2n

\boxed{T(n)=O(\log_2n)}

Recurrence Relation

Def a mapping from natural numme set.
A recurrence relation defines each term of tuence as a function of itsibonacci Relation

f(0)=0,f(1)=1

f(n)=f(n-1)+f\left(n-2\right)\quad\text{for }n\geq2

This is a classic recurrence relation.

General Form of Recurrence Relation

Let Is a sequence where an is term of the sequence then a relation of type

f(n)=a_{n}+c_1a_{n-1}+c_2a_{n-2}+\ldots+c_{k}a_{n-k},\quad n\geq k

is some functi, \dots, c_k$ are coner, called the degree ofinear recurrance relation with constant coefficient.

condition

Types of Recurrence Relations

Homogeneous Linear Recurrence Relation with constant coefficient

a_{n}+C_1a_{n-1}+C_2a_{n-2}+\ldots+C_{k}a_{n-k}=0\quad n\geq k

Inhomogeneous Linear Recurrence Relation with constant coefficient

f(n)=a_{n}+C_1a_{n-1}+C_2a_{n-2}+\ldots+C_{k}a_{n-k}\neq0

Examples of Recurrence Relation

	Homogeneous
	Inhomogeneous
	Inhomogeneous

Meaning of the Solution of a Recurrence Relation