CSI247:
Data Structures
Lecture 06 – Searching arrays
Department of Computer Science
B. Gopolang (247-275)
Learning Objectives
● By the end of this lecture, students must be:
• Use and implement linear search
• Use and implement Binary Search
2
A scenario
● Imagine the 2024/25 CSI247 classlist
● We can traverse this list to perform some operations
● Examples:
• Check whether student with ID number 20240123
is in the classlist
• Change name of student with ID 20230723 to
“Thomas Jones”
• Display details of student with ID 20249342
● The above operations require searching the classlist
3
Introduction
● Searching involves traversing a collection
• The process of looking for a specific element in a
collection
• E.g.: checking if a certain score is included in a list
of students’ marks
● Searching is one of the common task in programming
● The traversed collection can be:
• Ordered (sorted), or
• unordered
4
1. Searching
● Why search?
• To determine if an element is in a collection
• Or when we want to display/modify some
information about an element that is in a collection
(or delete the item, etc)
● Searching algorithms
• Linear search
• Binary search
5
a) Linear Search
● A simple algorithma) Linear Search
● Aka sequential search
● Compares search key with each element in the array
• Sequential comparison
• Until we find the value
• Or exhausts the collection
6
● What happens when search key is found?
• linear search returns index of the element
that matches the search item
● If no match:
• search returns -1.
● Note: For an ordered collection, there is no need
to look at all elements
• Can stop searching once we determine that the
element cannot be in the collection
7
i) Searching an unordered collection
● Searching for 18:
63 29 85 72 18 42 23 54 8 32
Outcome: FOUND!
- No. of comparisons?
18
8
● Searching for 31?
63 29 85 72 18 42 23 54 8 32
Outcome: NOT FOUND
31
- No. of comparisons?
9
ii) Searching an ordered collection
● Searching for 18:
8 18 23 29 34 42 54 63 72 85
Outcome: FOUND!
18 - No. of comparisons?
10
● Searching for 31:
8 18 23 29 34 42 54 63 72 85
Outcome: NOT FOUND!
31 - No. of comparisons?
11
Linear search implementation
● Write an iterative method that accepts an array of
integers and an integer value, then return an integer
representing the index where the value is stored if found.
Otherwise, the method should return -1.
● Soln?
● Q: What is linear search’s:
• Best-case runtime?
• Worst-case runtime?
● Convert the iterative method into a recursive one
12
Observation
● Sorted collection: searching is faster only if the
search key is not in the list
• Collection MUST be sorted
● In general, linear search’s efficiency is similar
when searching both unordered and ordered
collections
13
● Q:
• Isn’t there a more efficient approach for
ordered collections?
● A: There is!
• We need an approach that will reduce the
number of comparisons!
• Hence more efficient!
14
b) Binary Search
● Requires a sorted collection
● We keep on reducing search space by half
• Until we find search key
• OR we exhaust the collection
● Because it uses an ordered (sorted) collection,
we stop when we do not find the item where
we expect to find it
● Good for data structures that allow for random
access (E.g. arrays)
15
How does Binary Search operate?
● First, compare search key with the middle element
● K3 possible cases:
• Search key == middle element
• Found it, search ends
• Search key < middle element
• Search the key in the first half (Left) of the
array.
• Search key > middle element
• Search in the second half (Right) of the array.
16
● Search for 18:
42
0 1 2 3 4 5 6 7 8 9
Left of mid-point
Approximate mid-point
18 == mid-point key? NO.
18 < mid-point key? Yes.
Focus the search on the left side. (Ignore the R side)
--- See next slide ---
17
8 18 23 29 34
0 1 2 3 4
Left of mid-point
Approximate new mid-point
18 == mid-point key? NO.
18 < mid-point key? Yes.
Focus the search on the left side. (Ignore the R side)
--- See next slide ---
18
8 18
0 1
Approximate new midpoint
18 == midpoint key? YES.
Key found
Stop searching!
19
Observation
● Binary search reduces the work because it
divides the collection into 2
● We need to keep track of which “part” of
the array we are focusing on
20
Binary search implementation
● Write an iterative method that accepts an array of
integers, a search key and the relevant items, then return
an integer representing the index where the value is
stored if found. Otherwise, the method should return -1.
● Soln?
● Q: What is binary search’s:
• Best-case runtime?
• Worst-case runtime?
● Convert the iterative method into a recursive one
21
Summary
• In this lesson, we were able to do these:
• Linear search
• Binary search
22
Next lesson
• Sorting Arrays
23
Q &A
16
