Data structure unit I part B

Data Structure
 Unit-I Part B

Searching
 It is a method to find a element or data.
Searching Types
Linear Search Binary Search

List search
 The algorithm used to search a list depends to a large extent on the structure of
the list.
 The two basic searches for arrays are the sequential or linear search and binary
search.
 Sequential or Linear Search
 It can be used to locate an item in any array.
 Binary Search
 It requires on ordered list.

Sequential or Linear Search:
 Search in sequential order.
 It is used whether the list is not ordered.
 Example:
 It is used only for small lists or lists that aren’t searched often.
 We start searching for the target at the beginning of the list and continue until we
find the target.
 Termination Condition
 Target is found (Success)
 List of elements is exhausted or Target is not found (failure)

Algorithm
 Step 1: The list we are searching
 Step 2: An index to the last element in the list.
 Step 3: The target
 Step 4: The address where the found element’s index location is to be stored.
 Step 5: To tell calling algorithm whether data were located
 Step 6: We return a Boolean - true for we found it or false for we didn’t found it.
 Note: As an alternative to the index to the last element, the size of the list may be
passed.

Data Structures: A
Pseudocode
Approach with C,
Second Edition
9
Successful
search of an
unordered list

Data Structures: A
Pseudocode
Approach with C,
Second Edition
10
Unsuccessful
search in
unordered list

Data Structures: A
Pseudocode
Approach with C,
Second Edition
11
Sequential
search
algorithm

Variations on Sequential Search
 Three useful variations on the sequential search algorithm:
 The sentinel search
 The probability search
 The ordered list search

Sentinel Search
 Loop tests two conditions:
 End of list
 Target not found.
Knuth states that, “When the inner loop of a program tests two or more conditions, an
attempt should be made to reduce it to just one condition”
 The only way we can ensure that a target is actually in the list is to put it there our self.
 A target is put in the list by adding an extra element (sentinel entry) at the end of the array and
placing the target in the sentinel.
 We can then optimize the loop and determine after the loop completes whether we found actual
data or the sentinel.
 Disadvantage:
 The rest of the processing must be careful to never look at the sentinel element at the end of the
list.

Probability Search
 The array is ordered with the most probable search elements at the beginning of
the array and the least probable search elements at the end.
 It is especially useful when relatively few elements are the targets for most of the
searches.
 To ensure that the probability ordering is correct over time, in each search we
exchange the located element with the element immediately before it in the array.

Ordered List Search
 Although we generally recommend a binary search when searching a list ordered on the key
(target), if the list is small it may be more efficient to use a sequential search.
 When searching an ordered list sequentially, however, it is not necessary to search to the end of
the list to determine that the target is not in the list.
 We can stop when the target becomes less than or equal to the current element we are testing.
 In addition, we can incorporate the sentinel concept by bypassing the search loop when the
target is greater than the last item.
 In other words, when the target is less than or equal to the last element, the last element
becomes a sentinel, allowing us to eliminate the test for the end of the list.
 Although it can be used with array implementations, the ordered list search is more commonly
used when searching linked list implementations.

Binary Search
 The sequential search algorithm is very slow.
 If we have an array of 1000 elements, we must make 1000 comparisons in the worst case.
 If the array is not sorted, the sequential search is the only solution.
 It the array is sorted, we can use a more efficient algorithm called binary search.
 The binary search starts by testing the data in the element at the middle of the array.
 To determine if the target is in the first or the second half of the list.
 mid = (begin + end) / 2
 If it is in the first half, we do not need to check the second half. If it is in the second half, we
do not need to test the first half.

 To find the middle of the list, we need three variables:
 Step 1: One to identify the beginning of the list
 Step 2: One to identify the middle of the list
 Step 3: One to identify the end of the list.
 We analyze two cases here:
 The target is in the list
 The target is not in the list.

Data Structures: A
Pseudocode
Approach with C,
Second Edition
22
Binary
search
example



 




 

2
2
lastfirst
mid
endbegin
mid

Data Structures: A
Pseudocode
Approach with C,
Second Edition
24
Figure 2-5
Unsuccessful
binary
search
example

Data Structures: A
Pseudocode
Approach with C,
Second Edition
25

Data Structures: A
Pseudocode
Approach with C,
Second Edition
26
(continued)

Data Structures: A Pseudocode Approach with C, Second Edition 27
Analyzing search algorithms
The efficiency of the
sequential search is
O(n).
The efficiency of the
binary search is
O(log n).
List size Iterations
binary Sequential
(Average)
Sequential
(worst
case)
16 4 8 16
50 6 25 50
256 8 128 256
1000 10 500 1000
10000 14 5000 10000
100000 17 50000 100000
1000000 20 500000 1000000

 a) For Sequential Search The basic loop for the sequential search is shown below.
 The efficiency of the sequential search is O(n).
 The search efficiency for the sentinel search is basically the same as for the sequential search.
 Although the sentinel search saves a few instructions in the loop, its design is identical.
 Therefore, it is also an O(n).
 b) The binary search locates an item by repeatedly dividing the list in half.
 Its loop is:
 This loop obviously divides, and it is therefore a logarithmic loop.
 The efficiency is the binary search is O(log n).

Data structure unit I part B

Recommended

More Related Content

What's hot (11)

Similar to Data structure unit I part B (20)

More from SSN College of Engineering, Kalavakkam (20)

Recently uploaded (20)

Data structure unit I part B