7/13/2021
The Searching Problem
● The process of finding a particular element in an array is
called searching. There two popular searching techniques:
■ Linear search, and
■ Binary search.
● The linear search compares each element in an unsorted
array with the search key.
■ Running time: O(n)
● Given a sorted array, Binary Search algorithm can be used to
perform fast searching of a search key on the sorted array.
■ Running time: O(log n)
Dr. Md. Abul Kashem Mia, Professor, CSE Dept and Pro-Vice Chancellor, UIU 17
Linear Search
● Each member of the array is visited until the search key is
found.
● Example:
Write a program to search for the search key entered by the
user in the following array:
(9, 4, 5, 1, 7, 78, 22, 15, 96, 45)
You can use the linear search in this example.
Dr. Md. Abul Kashem Mia, Professor, CSE Dept and Pro-Vice Chancellor, UIU 18
9
Linear Search
def linear_search(arr, target): # Example usage:
arr = [10, 23, 45, 70, 11, 15]
for index in range(len(arr)): target = 70
if arr[index] == target: # Function call
return index result = linear_search(arr, target)
return -1
if result != -1:
print(f"Element found at index: {result}")
else:
print("Element not found in the array")
Binary Search
• Given a sorted array, Binary Search algorithm can be used to perform
fast searching of a search key on the sorted array.
• The following program implements the binary search algorithm for
the search key entered by the user in the following array:
(3, 5, 9, 11, 15, 17, 22, 25, 37, 68)
Iterative Code
def binary_search(arr, x): # Test array
low = 0 arr = [ 2, 3, 4, 10, 40 ]
high = len(arr) - 1 x = 10
mid = 0
while low <= high: # Function call
mid = (high + low) // 2 result = binary_search(arr, x)
if arr[mid] < x:
if result != -1:
low = mid + 1 print("Element is present at index", str(result))
elif arr[mid] > x: else:
high = mid - 1 print("Element is not present in array")
else:
return mid
return -1
Recursive Code
def binary_search(arr, low, high, x): # Test array
if high >= low: arr = [ 2, 3, 4, 10, 40 ]
x = 10
mid = (high + low) // 2
if arr[mid] == x: # Function call
return mid result = binary_search(arr, 0, len(arr)-1, x)
elif arr[mid] > x:
if result != -1:
return binary_search(arr, low, mid - 1, x) print("Element is present at index", str(result))
else: else:
print("Element is not present in array")
return binary_search(arr, mid + 1, high, x)
else:
return -1
7/13/2021
Sorting In Linear Time
Counting sort
No comparisons between elements!
But…depends on assumption about the numbers being
sorted
We assume numbers are in the range 1, …, k
The algorithm:
Input:A[1..n], where A[i] {1, 2, 3, …, k}
Output: B[1..n], sorted (notice: not sorting in place)
Also: Array C[1..k] for auxiliary storage
Dr. Md. Abul Kashem Mia, Professor, CSE Dept and Pro-Vice Chancellor, UIU
Counting Sort
COUNTING-SORT assumes that each of the input elements is an integer
in the range 0 to k, inclusive.
A [1..n] is the input array, B [1..n] is the output array, C [0..k] is a
temporary working array.
Dr. Md. Abul Kashem Mia, Professor, CSE Dept and Pro-Vice Chancellor, UIU
13
Counting Sort
def countingSort(arr): for m in range(1, 10):
size = len(arr) count[m] += count[m - 1]
output = [0] * size
m = size - 1
while m >= 0:
count = [0] * 10 output[count[arr[m]] - 1] = arr[m]
count[arr[m]] -= 1
for m in range(0, size): m -= 1
count[arr[m]] += 1
7/13/2021
Counting Sort: Example
Dr. Md. Abul Kashem Mia, Professor, CSE Dept and Pro-Vice Chancellor, UIU
Counting Sort
Why don’t we always use counting sort?
Because it depends on range k of elements
Could we use counting sort to sort 32 bit integers? Why
or why not?
Answer: No, k is too large (232 = 4,294,967,296)
Dr. Md. Abul Kashem Mia, Professor, CSE Dept and Pro-Vice Chancellor, UIU
15