Introduction To
Algorithms
Lecture 7 – Searching Algorithms
2nd Year, 2nd Semester – Musa Hodman
Winter, 2024
Outline
1 Linear Search
2 Binary Search
Linear Search in Array
Ann Pat ... Joe Bob
Linear Search in Array
Ann Pat ... Joe Bob
Linear Search in Array
Ann Pat ... Joe Bob
Linear Search in Array
Ann Pat ... Joe Bob
Linear Search in Array
Ann Pat ... Joe Bob
Linear Search in Array
Ann Pat ... Joe Bob
Linear Search in Array
Ann Pat ... Joe Bob
Real-life Example
english french italian german spanish
house maison casa Haus casa
car voiture auto Auto auto
table table tavola Tabelle mesa
Searching in an array
Input: An array A with n elements.
A key k.
Output: An index, i, where A[i] = k.
If there is no such i, then
NOT_FOUND.
Recursive Solution
LinearSearch(A, low , high, key )
Recursive Solution
LinearSearch(A, low , high, key )
if high < low :
return NOT_FOUND
if A[low ] = key :
return low
Recursive Solution
LinearSearch(A, low , high, key )
if high < low :
return NOT_FOUND
if A[low ] = key :
return low
return LinearSearch(A, low + 1, high, key )
Recursive Solution
LinearSearch(A, low , high, key )
if high < low :
return NOT_FOUND
if A[low ] = key :
return low
return LinearSearch(A, low + 1, high, key )
Definition
A recurrence relation is an equation
recursively defining a sequence of values.
Definition
A recurrence relation is an equation
recursively defining a sequence of values.
Fibonacci recurrence relation
⎧
⎨0 if n = 0
⎪
⎪
F (n) = 1 if n = 1
⎪
⎩F (n − 1) + F (n − 2) if n > 1
⎪
Definition
A recurrence relation is an equation
recursively defining a sequence of values.
Fibonacci recurrence relation
⎧
⎨0 if n = 0
⎪
⎪
F (n) = 1 if n = 1
⎪
⎩F (n − 1) + F (n − 2) if n > 1
⎪
0, 1, 1, 2, 3, 5, 8, . . .
LinearSearch(A, low , high, key )
if high < low :
return NOT_FOUND
if A[low ] = key :
return low
return LinearSearch(A, low + 1, high, key )
LinearSearch(A, low , high, key )
if high < low :
return NOT_FOUND
if A[low ] = key :
return low
return LinearSearch(A, low + 1, high, key )
Recurrence defining worst-case time:
T (n) = T (n − 1) + c
LinearSearch(A, low , high, key )
if high < low :
return NOT_FOUND
if A[low ] = key :
return low
return LinearSearch(A, low + 1, high, key )
Recurrence defining worst-case time:
T (n) = T (n − 1) + c
T (0) = c
Runtime of Linear Search
n
n−1
n−2
...
2
1
0
Runtime of Linear Search
work
n c
n−1 c
n−2 c
...
2 c
1 c
0 c
Runtime of Linear Search
work
n c
n−1 c
n−2 c
...
2 c
1 c
0 c
∑︀n
Total: i=0 c = Θ(n)
Iterative Version
LinearSearchIt(A, low , high, key )
for i from low to high:
if A[i] = key :
return i
return NOT_FOUND
Summary
Create a recursive solution
Summary
Create a recursive solution
Define a corresponding recurrence
relation, T
Summary
Create a recursive solution
Define a corresponding recurrence
relation, T
Determine T (n): worst-case runtime
Summary
Create a recursive solution
Define a corresponding recurrence
relation, T
Determine T (n): worst-case runtime
Optionally, create iterative solution
Outline
1 Linear Search
2 Binary Search
Searching Sorted Data
Searching in a sorted array
Input: A sorted array A[low . . . high]
(∀low ≤ i < high : A[i] ≤ A[i + 1]).
A key k.
Output: An index, i, (low ≤ i ≤ high) where
A[i] = k.
Otherwise, the greatest index i,
where A[i] < k.
Otherwise (k < A[low ]), the result is
low − 1.
Searching in a Sorted Array
Example
3 5 8 20 20 50 60
1 2 3 4 5 6 7
Searching in a Sorted Array
Example
search(2) → 0
3 5 8 20 20 50 60
1 2 3 4 5 6 7
Searching in a Sorted Array
Example
search(2) → 0
search(3) → 1
3 5 8 20 20 50 60
1 2 3 4 5 6 7
Searching in a Sorted Array
Example
search(2) → 0
search(3) → 1
search(4) → 1
3 5 8 20 20 50 60
1 2 3 4 5 6 7
Searching in a Sorted Array
Example
search(2) → 0 search(20) → 4
search(3) → 1
search(4) → 1
3 5 8 20 20 50 60
1 2 3 4 5 6 7
Searching in a Sorted Array
Example
search(2) → 0 search(20) → 4
search(3) → 1 search(20) → 5
search(4) → 1
3 5 8 20 20 50 60
1 2 3 4 5 6 7
Searching in a Sorted Array
Example
search(2) → 0 search(20) → 4
search(3) → 1 search(20) → 5
search(4) → 1 search(60) → 7
3 5 8 20 20 50 60
1 2 3 4 5 6 7
Searching in a Sorted Array
Example
search(2) → 0 search(20) → 4
search(3) → 1 search(20) → 5
search(4) → 1 search(60) → 7
search(90) → 7
3 5 8 20 20 50 60
1 2 3 4 5 6 7
BinarySearch(A, low , high, key )
BinarySearch(A, low , high, key )
if high < low :
return low − 1
BinarySearch(A, low , high, key )
if high < low :
⌊︁ low − 1
return ⌋︁
high−low
mid ← low + 2
BinarySearch(A, low , high, key )
if high < low :
⌊︁ low − 1
return ⌋︁
high−low
mid ← low + 2
if key = A[mid]:
return mid
BinarySearch(A, low , high, key )
if high < low :
⌊︁ low − 1
return ⌋︁
high−low
mid ← low + 2
if key = A[mid]:
return mid
else if key < A[mid]:
return BinarySearch(A, low , mid − 1, key )
BinarySearch(A, low , high, key )
if high < low :
⌊︁ low − 1
return ⌋︁
high−low
mid ← low + 2
if key = A[mid]:
return mid
else if key < A[mid]:
return BinarySearch(A, low , mid − 1, key )
else:
return BinarySearch(A, mid + 1, high, key )
Example: Searching for the key 50
1 2 3 4 5 6 7 8 9 10 11
3 5 8 10 12 15 18 20 20 50 60
Example: Searching for the key 50
BinarySearch(A, 1, 11, 50)
1 2 3 4 5 6 7 8 9 10 11
3 5 8 10 12 15 18 20 20 50 60
low high
Example: Searching for the key 50
BinarySearch(A, 1, 11, 50)
1 2 3 4 5 6 7 8 9 10 11
3 5 8 10 12 15 18 20 20 50 60
low mid high
Example: Searching for the key 50
BinarySearch(A, 1, 11, 50)
BinarySearch(A, 7, 11, 50)
1 2 3 4 5 6 7 8 9 10 11
3 5 8 10 12 15 18 20 20 50 60
low mid high
Example: Searching for the key 50
BinarySearch(A, 1, 11, 50)
BinarySearch(A, 7, 11, 50)
1 2 3 4 5 6 7 8 9 10 11
3 5 8 10 12 15 18 20 20 50 60
low mid high
Example: Searching for the key 50
BinarySearch(A, 1, 11, 50)
BinarySearch(A, 7, 11, 50)
BinarySearch(A, 10, 11, 50)
1 2 3 4 5 6 7 8 9 10 11
3 5 8 10 12 15 18 20 20 50 60
low mid high
Example: Searching for the key 50
BinarySearch(A, 1, 11, 50)
BinarySearch(A, 7, 11, 50)
BinarySearch(A, 10, 11, 50)
1 2 3 4 5 6 7 8 9 10 11
3 5 8 10 12 15 18 20 20 50 60
low mid high
Example: Searching for the key 50
BinarySearch(A, 1, 11, 50)
BinarySearch(A, 7, 11, 50)
BinarySearch(A, 10, 11, 50) → 10
1 2 3 4 5 6 7 8 9 10 11
3 5 8 10 12 15 18 20 20 50 60
Summary
Summary
Break problem into non-overlapping
subproblems of the same type.
Summary
Break problem into non-overlapping
subproblems of the same type.
Recursively solve those subproblems.
Summary
Break problem into non-overlapping
subproblems of the same type.
Recursively solve those subproblems.
Combine results of subproblems.
BinarySearch(A, low , high, key )
if high < low :
⌊︁ low − 1
return ⌋︁
high−low
mid ← low + 2
if key = A[mid]:
return mid
else if key < A[mid]:
return BinarySearch(A, low , mid − 1, key )
else:
return BinarySearch(A, mid + 1, high, key )
Binary Search Recurrence Relation
(︁⌊︁ n ⌋︁)︁
T (n) = T +c
2
Binary Search Recurrence Relation
(︁⌊︁ n ⌋︁)︁
T (n) = T +c
2
Binary Search Recurrence Relation
(︁⌊︁ n ⌋︁)︁
T (n) = T +c
2
T (0) = c
Runtime of Binary Search
n
n/2
n/4
...
2
1
0
Runtime of Binary Search
work
n c
n/2 c
n/4 c
...
2 c
1 c
0 c
Runtime of Binary Search
work
n c
n/2 c
n/4 c
...
2 c
1 c
0 c
∑︀log2 n
Total: i=0 c = Θ(log2 n)
Iterative Version
BinarySearchIt(A, low , high, key )
while low⌊︁ ≤ high: ⌋︁
high−low
mid ← low + 2
Iterative Version
BinarySearchIt(A, low , high, key )
while low⌊︁ ≤ high: ⌋︁
high−low
mid ← low + 2
if key = A[mid ]:
return mid
Iterative Version
BinarySearchIt(A, low , high, key )
while low⌊︁ ≤ high: ⌋︁
high−low
mid ← low + 2
if key = A[mid ]:
return mid
else if key < A[mid ]:
high = mid − 1
Iterative Version
BinarySearchIt(A, low , high, key )
while low⌊︁ ≤ high: ⌋︁
high−low
mid ← low + 2
if key = A[mid ]:
return mid
else if key < A[mid ]:
high = mid − 1
else:
low = mid + 1
Iterative Version
BinarySearchIt(A, low , high, key )
while low⌊︁ ≤ high: ⌋︁
high−low
mid ← low + 2
if key = A[mid ]:
return mid
else if key < A[mid ]:
high = mid − 1
else:
low = mid + 1
return low − 1
Real-life Example
english french italian german spanish
house maison casa Haus casa
chair chaise sedia Sessel silla
pimple bouton foruncolo Pickel espenilla
Real-life Example
english french italian german spanish
(sorted) (sorted) (sorted) (sorted) (sorted)
chair chaise casa Haus casa
house bouton foruncolo Pickel espenilla
pimple maison sedia Sessel silla
Real-life Example
english french italian german spanish
house maison casa Haus casa
chair chaise sedia Sessel silla
pimple bouton foruncolo Pickel espenilla
english spanish
sorted sorted
2 1
1 3
3 2
Real-life Example
english french italian german spanish
house maison casa Haus casa
chair chaise sedia Sessel silla
pimple bouton foruncolo Pickel espenilla
english spanish
sorted sorted
2 1
1 3
3 2
Real-life Example
english french italian german spanish
house maison casa Haus casa
chair chaise sedia Sessel silla
pimple bouton foruncolo Pickel espenilla
english spanish
sorted sorted
2 1
1 3
3 2
Real-life Example
english french italian german spanish
house maison casa Haus casa
chair chaise sedia Sessel silla
pimple bouton foruncolo Pickel espenilla
english spanish
sorted sorted
2 1
1 3
3 2
Real-life Example
english french italian german spanish
house maison casa Haus casa
chair chaise sedia Sessel silla
pimple bouton foruncolo Pickel espenilla
english spanish
sorted sorted
2 1
1 3
3 2
Real-life Example
english french italian german spanish
house maison casa Haus casa
chair chaise sedia Sessel silla
pimple bouton foruncolo Pickel espenilla
english spanish
sorted sorted
2 1
1 3
3 2
Real-life Example
english french italian german spanish
house maison casa Haus casa
chair chaise sedia Sessel silla
pimple bouton foruncolo Pickel espenilla
english spanish
sorted sorted
2 1
1 3
3 2
Summary
Summary
The runtime of binary search is Θ(log n).
