Searching Lesson Plan - 6. Contents Evocation Objective Introduction Sequential Search Algorithm Variations on sequential search Mind map Summary. - презентация

1 Searching Lesson Plan - 6

2 Contents Evocation Objective Introduction Sequential Search Algorithm Variations on sequential search Mind map Summary

3 ANNEXURE-I Evocation

4 Evocation

5 Objective To learn the basics of sequential search algorithm To understand about the variations on sequential search

6 ANNEXURE-II Introduction -Sequential Search Searching is the process used to find location of target among a list of objects Example: Table of Employee Record Two basic searches for arrays are sequential search and binary search Sequential search is used to locate items in any array Binary search requires an ordered list

7 Sequential Search Sequential search is used whenever list is not ordered Start searching for the target at the beginning of list and continue until it finds the target or hits at the end of list Search algorithm requires four parameters List we are searching Index to last element in list Target Address where the found elements index location is to be stored

8 Successful Search of Unordered List

9 Unsuccessful Search of Unordered List

10 Sequential Search Algorithm

11 ANNEXURE-III Yoga Breathing Mudra

12 Yoga Breathing Mudra Enhances effortless breathing while gently balances five chakras Place your fingers in this position Thumb, middle, little finger gently pressed together (palm to palm) Both index fingers move behind the middle finger (dont strain) Right ring finger in front of left (increases inhale in 80% of people) Left ring finger in front of right (increase exhale in 80% of people) Whenever you inhale or exhale change the position of your ring finger Now allow yourself to breathe into your abdomen first with the breath flowing like a wave opening up your chest Allow your shoulders to remain relaxed. As you exhale, smile

13 Optical illusion Is the center square of stars standing still or moving?

14 Logo identification

15 Hidden Picture Puzzles

16 Variations on Sequential Search Three useful variations in sequential search algorithm are Sentinel search Probability search Ordered list search Sentinel Search Knuth states, when inner loop of program test two or more conditions, we should try to reduce testing to just one condition Target is put in list by adding extra element at end of array and place the target in sentinel Optimize the loop and determine after loop completes whether actual data found or sentinel

17 Variations on Sequential Search Probability Search Data in array are arranged with most probable search elements at beginning of array and least probable at end If probability ordering is correct over time, in each search exchange located element with element immediately before in array Ordered list search Search ordered list sequentially, it is not necessary to search to end of list to determine the target is not in the list Stop the target become less than or equal to current element we are testing

18 Sentinel Search Algorithm int find(int* a, int l, int v) { a[l] = v; // add sentinel value for (i = 0; ; i++) if (a[i] == v) { if (i == l) // sentinel value, not real result return -1; return i; }

19 Probability Search INPUT: list[] : reference of interger array last : index of last item target: target to be found ref_locn: reference to the location of target OUT: If target is found location of target is stored in ref_locn found = 1 is returned target is moved up in priority Else last is stored in ref_locn found = 0 is returned

20 Ordered List Search Algorithm OrderedListSearch(list, last, target, locn) if (target less than last element in list) find first element less than or equal to target set locn to index of element else set locn to last end if if (target in list) set found to true else set found to false end if return found end OrderedListSearch

21 Search Algorithm Advantages Easy algorithm to understand Array can be any order Easy to implement Can be used on very small data sets Not practical for searching large collections Disadvantage Inefficient (slow) for array of N elements, examine N/2 elements on average for value in array, N elements for value not in array

22 ANNEXURE-IV Mind Map Sequential Search Successful Search of Unordered list Unsuccessful Search of Unordered list Algorithm Variations of Sequential Search Sentinel Search Probability Search Ordered List Search

23 ANNEXURE-V Summary Searching is the process used to find location of target among a list of objects There are two basic methods for searching arrays: sequential search and binary search Sequential search is normally used when list is not sorted Starts at beginning of list and searches until it finds data or hits end of list

24 Summary In sentinel search, condition will end the search is reduced to only one by inserting target at end of list In probability search, list is sorted with most probable elements at beginning of list and least probable at end In order list search, it is not necessary to search to end of list to determine the target is not in the list