Search
Algorithms
WMSU
WESTERN MINDANAO STATE UNIVERSITY
Topic Outline
• Searching is the process of determining whether or not a
given value exists in a data structure or a storage media.
We discuss 3 searching methods on one-dimensional
arrays:
– Linear Search
• Sorted
• Unsorted
– Binary Search
– Interpolation Search
Linear Search
• The linear (or sequential) search algorithm on an array is:
– Sequentially scan the array, comparing each array item with
the searched value.
– If a match is found; return the index of the matched element;
otherwise return –1.
• Complexity: O(N)
Note: linear search can be applied to both sorted and
unsorted arrays.
Linear Search
Linear Search
Linear Search
• Python Pseudocode - Given an Array as arr[], and a
search item as key, go through each element in arr[]
and check if the element matches the key
For each item in array[]
if key = item
return item
Binary Search
• Binary search uses a recursive or an iterative method
to search an array to find a specified value
• The array must be a sorted array!!
– If the value is found, its index is returned
– If the value is not found, -1 is returned
• Complexity: O(log N)
Note: Each execution of the recursive method reduces the
search space by about a half
Binary Search
Low First, Determine
Mid = 0the Midpoint
+ (9 – 0) / 2 by using
theMid
formula: High
=4
mid = low
(Integers have+ no
(high - low) Places)
Decimal /2
Binary Search
• Now we have to check if the Item we’re searching for is Equal to
Mid (key == mid)
• If not, then we check:
– If our key is Less than Mid (key < mid) then set Mid – 1 as the NEW High
– If our key is Greater than Mid (key > mid) then set Mid + 1 as the NEW Low
Binary Search
• In our example, our key is greater than mid
Binary Search
• check if the Item we’re searching for is Equal to Mid (key == mid)
We assign mid
New+Low1 as=the
5 NEW low
• If not, then we check:
And again find Mida New
= 5 +mid
(9 –using
5) / 2the formula:
– If our key is Less than Mid (key < mid) then set Mid – 1 as the NEW High
mid = lowMid+ (high
= 7 - low) / 2
– If our key is Greater than Mid (key > mid) then set Mid + 1 as the NEW Low
New High = 6
Mid = 5 + (6 – 5) / 2
Mid = 5 + ½
Mid = 5
Binary Search
Binary Search
MyArray ← sorted array
n ← size of array
key ← value to be searched
lowerBound = 0
upperBound = n – 1 #Note that Arrays start at 0, so the size of array should be n - 1
while key not found
if upperBound < lowerBound
x does not exists.
compute midPoint = lowerBound + ( upperBound - lowerBound ) / 2 #Our formula for finding mid
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midpoint
Interpolation Search
• The Interpolation Search is an improvement over Binary
Search for instances, where the values in a sorted array
are uniformly distributed.
• It just uses a different formula for finding the midpoint
• Interpolation search may go to different locations
according to the value of the key being searched.
• Formula is instead:
mid = low + ((x – A[low]) * (high – low) / (A[high] – A[low]))
Interpolation Search
• Step1: In a loop, calculate the value of “pos” using the
probe position formula.
• Step2: If it is a match, return the index of the item, and exit.
• Step3: If the item is less than arr[pos], calculate the probe
position of the left sub-array. Otherwise, calculate the same
in the right sub-array.
• Step4: Repeat until a match is found or the sub-array
reduces to zero.
