VJC Chapter 11 Search Algorithms

VJC/H2Computing/9569 Chapter 11: Search Algorithms Contents 1 Introduction to Search Algorithms 2 Linear Search algorithm 2.1 Linear Search Algorithm in a List Using For-loop 2.2 Linear Search Algorithm in a List using while-loop 2.3 Complexity Analysis of Linear Search 2.4 Advantages of Linear Search 2.5 Drawbacks of Linear Search 3 Binary Search algorithm 3.1 Binary Search Using Iterative Loop 3.2 Binary Search using Recursive Function 3.3 Complexity Analysis of Binary Search 3.4 Advantages of Binary Search 3.5 Drawbacks of Binary Search 4 Conclusion Annex Syllabus Learning Outcomes 1.2 Fundamental Algorithms Understand algorithms for sorting and searching methods such as insertion sort, bubble sort, quicksort, merge sort, linear search, binary search and hash table search, and use examples to explain these methods. 1.2.3 Implement search algorithms. – Linear search – Binary search – Hash table search 1.2.4 Use examples to explain search algorithms. 1.2.5 Compare and describe the efficiencies of the search algorithms using Big-O notation for time complexity (worst case). Exclude: space complexity 2.3 Implementing Algorithms and Data Structures Use programming language elements and constructs to implement sort and search algorithms such as insertion sort, bubble sort, quicksort, merge sort, linear search, binary search and hash table search, as well as data structures such as stacks, queues, linear linked lists and binary search trees. 2.3.2 Implement search programs. – Linear search – Binary search – Hash table search

VJC/H2Computing/9569 1 Introduction to Search Algorithms A search algorithm is an algorithm that check for the existence of an element or to retrieve an element from any data structure where it is stored. There are two common types of search algorithms. ● Linear Search ● Binary Search 2 Linear Search algorithm Linear Search is a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set. It is one of the simplest searching algorithms and it commonly uses for-loop or while-loop to iterate through the collection. Example: Find 20 2.1 Linear Search Algorithm in a List Using For-loop Pseudocode of the linear search algorithm: FUNCTION linear_search(A: LIST, target: INTEGER) RETURNS INTEGER FOR i 0 TO length of A – 1 IF target = A[i] THEN RETURN i EN