Topics covered in this snacksized chapter:
Searching Algorithms are closely related to the concept of dictionaries.
Dictionaries are data structures that support:
A search algorithm is for finding an item with specified properties among a collection of items.
The items may be stored individually as records in a database.
Finding a particular piece of data in a data structure.
Example:
 Find the student who is named “Tom” from an array of students.
Sequential Search
Binary Search
Breadth First Search
Depth First Search
A sequential search of a list begins at the beginning of the list and continues until the item is searched.
This is a method for finding a particular value in a list that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.
UnorderedLinearSearch [A, n, x]:
for i ← 1 to n
do if A[i] = x
then return i
else i ← i + 1
return “x not found”
OrderedLinearSearch [A, n, x]:
for i ← 1 to n
do if A[i] = x
then return i
else if A[i] < x
then i ← i + 1
else return “x not found”
return “x not found”
Search for an element 2 in the list below using sequential search.
Solution:
 Search element 2 is found.
Binary search looks for an item in a list using a divide and conquer strategy.
The binary search algorithm assumes that the items in the array being searched are sorted.
The algorithm begins at the middle of the array in a binary search.
If the item for which we are searching is less than the middle, then it must reside in the top half of the array.
The search stops when the value has been found (or when it has been shown that the value does not appear on the list).
At each stage, half of the remaining list is discarded.
Step 1
 The algorithm compares the search value with the middle value in the list.
 Either
The search value is found to be at this position.
Or
The search value occurs before the middle of the list.
Or
The search value occurs after the middle of the list.

Step 2
 If (a) occurs, the search is over.


If (b) occurs, the search continues with Step 1 on a reduced list.
 Consisting of those values before the middle value.

If (c) occurs, the search continues with Step 1 on a reduced list.
 Consisting of those values after the middle value.

Example:
 Perform a binary search for 8 in a given array (6 8 12 20 22).
Given a value and sorted array a [ ], find the index such that .
Step 1:
Step 2:
 The middle value is 12, so the search value 8 occurs before 12.
Step 3:
Step 4:
Step 5:
 Middle value is 8 which is the required search value.
Step 6: