Linear & Binary Search
Course Code: CSC 2211 Course Title: Algorithms
Dept. of Computer Science
Faculty of Science and Technology
Lecturer No: 4 Week No: 2 Semester: Fall 23-24
Lecturer: Dr. Mohammad Rabiul Islam; Email: rabiul.islam@aiub.edu
Lecture Outline
1. Searching
• Linear Search
• Binary Search
Searching
Introduction
Search: locate an item in a list of data/information.
Two approaches will be discussed…
1. Linear or Sequential Search:
• Searches sequentially for an element.
• Starts from the first element.
2. Binary Search:
• Searches an element by dividing the sorted elements in a list into two
sub-list
• Starts with the middle element.
Linear Search
Algorithm and Simulation
Algorithm:
Input: Array, #elements, item (to search)
Start with the element at index = 0
Step 1: Compare the element at index with item. If its equal to item then return
index with status “Found” otherwise go to step 2.
Step 2: Increase index by 1. If index is less than #elements go to step 1
otherwise return -1 with status “Not found”.
indexindex
indexindex
indexindex value 11
0 1 2 3 4 5 6 7 8 9 found false
true
33 66 22 111 77 11 99 55 88 44 position -1
5
Linear Search Algorithm
int SearchItem(int arr[], int n, int
x)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == x)
{
return i;
}
}
return -1;
}
Linear Search Complexity
Linear Search Complexity
for (int i = 0; i < n; i++) { n
if (arr[i] == x) c1
{
return i;
}
}
Extra: c2
So, T(n) = O(1) when n = 1, and
n*c1+ c2 when n > 1
skipping the unnecessary terms
T(n)= O(n)
Binary Search
Pseudocode
Process:
1. Start with f_index = 0 and l_index = size-1
2. The value of m_index will be (f_index+l_index)/2.
3. Compare the value of item with arr[m_index].
(a)If item < arr[m_index], l_index will be m_index-1.
(b)Else if item > arr[m_index], f_index will be m_index+1.
(c) Else, position will be m_index. Exit.
4. Repeat (2), (3) till f_index<= l_index.
Binary
Binary Search Algorithm Search
int m_index, position=-1, f_index=0,l_index=size-
1;;
while(f_index<=l_index){
m_index=(f_index+l_index/)2;
if(item<arr[m_index]){
l_index=m_index-1;
}
else if(item>arr[m_index]){
f_index=m_index+1;
}
else{
position=m_index;
}
}
Binary Search
Simulation
last last last
value 77
60
first first
first
first 0
6
5
last 9
6
4 11 22 33 44 55 66 77 88 91 99
middle 7
5
6
4 0 1 2 3 4 5 6 7 8 9
found
not found middle
middle middle
middle
Binary Search Complexity
Binary Search Algorithm Complexity
bSearch(arr, x, low, high) T(n), to sort n
elements
if low > high c1
return False
else
mid = (low + high) / 2
if x == arr[mid] T(1)
return mid
else if x > arr[mid]
return bSearch(arr, x, mid + 1,
high) T(n/2)
else
return bSearch(arr, x, low, mid -
1)
So, T(n) = O(1) when n = 1, and T(n/2)
+ T(1) + c1 when n > 1
Binary Search Complexity
Runtime
Class work
Find out the complexity using the following methods
1. Repeated substitution method
2. Recursion Tree method
Search
Analysis
Binary search is more efficient than linear search.
For array of N elements, performs at most comparisons.
Disadvantages: Requires that array elements to be
sorted.
References
1. https://en.wikipedia.org/wiki/Insertion_sort
2. https://en.wikipedia.org/wiki/Sorting_algorithm
3. Nice animations are available here
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
4. https://en.wikipedia.org/wiki/Linear_search
5. https://en.wikipedia.org/wiki/Binary_search_algorithm
Books
“Schaum's Outline of Data Structures with C++”. By John R. Hubbard
“Data Structures and Program Design”, Robert L. Kruse, 3rd Edition, 1996.
“Data structures, algorithms and performance”, D. Wood, Addison-Wesley, 1993
“Advanced Data Structures”, Peter Brass, Cambridge University Press, 2008
“Data Structures and Algorithm Analysis”, Edition 3.2 (C++ Version), Clifford A.
Shaffer, Virginia Tech, Blacksburg, VA 24061 January 2, 2012
“C++ Data Structures”, Nell Dale and David Teague, Jones and Bartlett Publishers,
2001.
“Data Structures and Algorithms with Object-Oriented Design Patterns in C++”,
Bruno R. Preiss,
