# Chapter 10 : Searching

### Topics covered in this snack-sized chapter:

#### Searching Algorithms arrow_upward

• Searching Algorithms are closely related to the concept of dictionaries.
• Dictionaries are data structures that support:
• Search operations
• Insert operations
• Delete operations
• 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.

• #### Uses of Searching Algorithms arrow_upward

• Finding a particular piece of data in a data structure.
• Example:
• Find the student who is named “Tom” from an array of students.

#### Types of Searching Algorithms arrow_upward

• Sequential Search
• Binary Search
• Depth First Search

• #### Sequential Search arrow_upward

• 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.

• #### Example of a Searching Algorithm arrow_upward

###### Unordered-Linear-Search [A, n, x]:
```for i ← 1 to n
do if A[i] = x
then return i
else i ← i + 1
```

###### Ordered-Linear-Search [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
```
###### Example:

• Search for an element 2 in the list below using sequential search.

•  5 20 9 4 2 18

• Solution:
• Search element is 2.

• Search element 2 is found.

#### Binary Search arrow_upward

• Binary search looks for an item in a list using a divide and conquer strategy.

• #### Binary Search Rules arrow_upward

• 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.

• #### Algorithm for Binary Search arrow_upward

 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:
• Search terminates.

#### Thank You from Kimavi arrow_upward

• Please email us at Admin@Kimavi.com and help us improve this tutorial.

• Kimavi - A Video Learning Library { Learning is Earning }

Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only \$10 a month