Searching Algorithms
Searching Algorithms
Necessary components to search a list of data
◦ Array containing the list
◦ Length of the list
◦ Item for which you are searching
After search completed
◦ If item found, report “success,” return location in array
◦ If item not found, report “not found” or “failure”
Searching Algorithms (Cont’d)
• Suppose that you want to determine whether 27 is in the list
Figure 1: Array list with seven (07) elements
Method
• First compare 27 with list[0]; that is, compare
27 with 35
• Because list[0] ≠ 27, you then compare 27
with list[1]
• Because list[1] ≠ 27, you compare 27 with
the next element in the list
• Because list[2] = 27, the search stops
• This search is successful!
Searching Algorithms
Let’s now search for 10 ………………
……………………………………..
Eventually, no more data is left in the list to
compare with the search item; this is an
unsuccessful search
Write a code or pseudo
code
Performance of the Linear Search
Performance of the Linear Search
(Cont’d)
• Therefore, the best case is: 1
• And, the worst case is: N
• The average case is:
Worst case and key found at the end of
the array list!
Best case
Average Number of
1 + 2 + 3 + …..+ N + N
=
Comparisons
N+1
Worst case and key is NOT found!
Number of possible cases
Binary Search Algorithm
Can only be performed on a sorted list !!!
Uses divide and conquer technique to search list
Binary Search Algorithm (Cont’d)
Search item is compared with middle element of
list
If search item < middle element of list, search
is restricted to first half of the list
If search item > middle element of list, search
second half of the list
If search item = middle element, search is
complete
Binary Search Algorithm (Cont’d)
• Determine whether 75 is in the list
Figure 2: Array list with twelve (12) elements
Figure 3: Search list, list[0] … list[11]
Binary Search Algorithm (Cont’d)
Figure 4: Search list, list[6] … list[11]
Binary Search Algorithm (Cont’d)
public static int binarySearch(int[] list, int listLength, int key) {
int first = 0, last = listLength - 1;
int mid;
boolean found = false;
while (first <= last && !found) {
mid = (first + last) / 2;
if (list[mid] == key)
found = true;
else
if(list[mid] > key)
last = mid - 1;
else
first = mid + 1;
}
if (found)
return mid;
else
return –1;
} //end binarySearch
For a list of n elements, Binary Search
can execute at most log2 n times!!
Linear Search, on the other hand, can
execute up to n times !!
◦ For a list of n elements, Binary Search can
execute at most log2 n times!!
Order of growth =O(lg n)
◦ Linear Search, on the other hand, can execute up
to n times !! …………………O(n)
Average Number of Iterations
Length Linear Search Binary Search
10 5.5 2.9
100 50.5 5.8
1,000 500.5 9.0
10,000 5000.5 12.0
Is Binary Search more
efficient?
Number of computations per iteration:
◦ Binary search does more computations than
Linear Search per iteration.
Overall:
◦ If the number of components is small (say, less
than 20), then Linear Search is faster.
◦ If the number of components is large, then Binary
Search is faster.
17
Advantages of a linear search
Will perform fast searches of small to
medium lists. With today's powerful
computers, small to medium arrays can be
searched relatively quickly.
The list does not need to sorted. ...
Not affected by insertions and deletions.
