Searching & Algorithms IN DATA STRUCTURES

Searching & Algorithms IN DATA STRUCTURES

TOPICS INCLUDED:
1. Sequential search
2. Binary search
3. Linear search
4. List search

1. Searching & Algorithms Rakshit Dogra CSE/23/112

2. Searching ! T he process of finding a given value position in a list of values

3. What is Searching? Definition of Search : Search is the process of determining whether an element with a specific value exists within a given set. Purpose of Searching : It aims to find out if a particular element is present in a list. Role of Search Algorithms : Search algorithms are designed to locate a single element from a set using a key, which includes additional information relevant to that element. Types of Lists and Search Methods : Unordered Lists: For lists that are not sorted, linear or sequential search is employed. Ordered Lists: When the list is sorted, binary search is used to efficiently locate elements.

4. Searching Terminologies Internal key Key is contained within the record at a specific offset from the start of the record External Key There is a separate table of keys that includes pointers to the records Primary Key The key used to search is unique for every record in the table Secondary Key Same key may be associated with more than one record in the table Search algorithm Accepts an argument and tries to find a record in a given table whose key it matches.

5. Searching Terminologies Successful search Algorithm finds at least one record Unsuccessful search Algorithm doesn’t find any records Retrieval A successful search is often called retrieval. Internal Searching Records to be searched are sorted entirely within computer main memory External Searching For large records we need external storage devices and we search on such devices.

6. Search Algorithm A search algorithm accepts a key as an argument and attempts to find a record in a given data that matches this key. Terminologies: Successful Search : The algorithm finds at least one record. Unsuccessful Search : The algorithm does not find any records. Retrieval : A successful search is often termed retrieval. Internal Searching : Records that need to be searched are sorted entirely within the computer's main memory. External Searching : For larger datasets, external storage devices are used, and searches are conducted on such devices.

7. LIST SEARCH F inding an element in a data collection

8. List Search List search is a fundamental concept in computer science that involves locating an element within a collection of data (a list). It serves as the foundation for various searching algorithms, such as sequential search and binary search. Understanding list search is essential for implementing efficient search operations in software development and data processing.

9. List Search Definition List search refers to the method of finding a specific element in a list. This process can vary depending on whether the list is ordered (sorted) or unordered (unsorted). The search can be performed using different algorithms, each with its advantages and performance characteristics. Types of List Searches Sequential Search (Linear Search) Binary Search

10. Binary Search 01 02 Types of Searching Algorithms Sequential Search (Linear Search)

11. 01 Sequential Search

12. The Definition Sequential search, also known as linear search, is the simplest search algorithm. It involves examining each element of the list sequentially until the desired element is found or the end of the list is reached.

13. Functionality - Sequential Search How it Works : Start from the first element of the list. Compare the target element with the current element. If a match is found, return the index of that element. If the end of the list is reached without finding a match, return an indication that the element is not present.

14. Details - Sequential Search Example : For an unsorted list like [10, 15, 30, 70, 80] , to find 15 : Compare 10 with 15 (not a match). ✗ Continue until 15 is found. Compare 15 with 15 (a match). ✓

15. Linear Search - Algorithm Let a[n] be an array of size n and x be an item to be searched. The search starts from the first element and proceeds sequentially through the array. Set i = 0 (starting index). While i < n: If a[i] == x: Return i (the index where x is found). If the end of the array is reached (i == n) and x is not found: Return -1 (indicating that the element is not present).

16. Performance - Sequential Search Time Complexity: Best Case: O(1) (element is at the first position) Average Case: O(n) Worst Case: O(n) (element is not present or is at the last position) Space Complexity: O(1) (only requires a constant amount of additional space)

17. 02 Binary Search

18. The Definition Binary search is a more efficient search algorithm that operates on sorted lists. It significantly reduces the number of comparisons needed to find an element.

19. Functionality - Binary Search How it Works Find the middle element of the list. Compare the middle element with the target element. If they match, the search is successful. If the target is less than the middle element, repeat the search in the left half. If the target is greater, repeat in the right half. Continue this process until the element is found or the search area is exhausted.

20. Functionality - Binary Search Example: For a sorted list like [10, 12, 27, 34, 46, 56], to find 46: Middle element is 27. Since 46 > 27, search the upper half: [34, 46, 56]. New middle is 46 (found).

21. Binary Search - Algorithm Let a[n] be a sorted array of size n and x be the item to be searched. Let low = 0 and high = n-1 be the lower and upper bounds of the array. While low <= high: Set mid = (low + high) / 2 (calculate the middle index). If a[mid] == x: Return mid (the index where x is found). If x < a[mid]: Set high = mid - 1 (search in the left half of the array). Else: Set low = mid + 1 (search in the right half of the array). If the search area is exhausted (low > high): Return -1 (indicating that the element is not present).

22. Performance - Binary Search Time Complexity : Best Case: O(1) (element is at the middle) Average Case: O(log n) Worst Case: O(log⁡ n) (element not found) Space Complexity : Iterative Implementation: O(1) Recursive Implementation: O(log ⁡n) (due to recursion stack)

23. Advantages & Disadvantages of Binary Search Advantages Disadvantages Faster than linear search, especially for large arrays Requires the array to be sorted More efficient than similar algorithms like interpolation or exponential search Needs data stored in contiguous memory locations Suitable for large datasets stored in external memory (e.g., hard drives, cloud) Requires elements to be comparable (must be able to be ordered)

24. Comparison of Search Methods Relationship Between List Search and Search Algorithms Foundation : List search provides the basis for understanding how elements can be located within a dataset. It encapsulates both sequential and binary searches, each tailored to different data arrangements. Sequential vs. Binary: Sequential Search : Best suited for small or unsorted lists due to its simplicity and ease of implementation. However, its performance degrades as the list size increases. Binary Search : Ideal for large, sorted datasets as it dramatically reduces the number of comparisons needed, making it much more efficient than sequential search.

25. Efficiency in Time Complexity O(log ⁡n) O(n) Linear Search Binary Search More Efficient Less Efficient Comparison

26. Iterative Binary Search Algorithm 01 02 Types of Binary Search Recursive Binary Search

27. 01 Recursive Binary Search

28. Recursive Binary Search The list is divided into two halves, and the search begins by comparing the target with the middle element. If the target is smaller, the search continues in the first half; if larger, in the second half. This process repeats until the target is found or only one element remains.

29. RBS - Algorithm Let a[n] be a sorted array of size n and x be an item to be searched. Let low=0 and high=n-1 be lower and upper bound of an array 1. If (low>high) return O; 2. mid=(low+high)/2; 3. if (x==a[mid]) return mid; 4. if (x<a[mid]) Search for x in a[low] to a[mid-1]; 5. Else Search for x in a[mid+1] to a[high];

30. RBS - Algorithm Solved We need to search 46, we can assign first=0 and last= 9 since first and last are the initial and final position/index of an array The binary search when applied to this array works as follows: Find center of the listi.e. (first+last)/2 =4 i.e. mid=array[4]=10 If higher than the mid element we search only on the upper half of an array else search lower half. In this case since 46>10, we search the upper half i.e. array[mid+1] to array [n-1] The process is repeated till 46 is found or no further subdivision of array is possible

31. 02 Iterative Binary Search Algorithm

32. Iterative Binary Search The recursive algorithm is often unsuitable in practical scenarios where efficiency is crucial. Below is the non-recursive version of the binary search algorithm. Let a[n] represent a sorted array of size n, and key be the item being searched for.

33. I BS - Algorithm BinarySearch(a[], key, n): low = 0 hi = n - 1 while (low <= hi): mid = (low + hi) if (key == a[mid]): return mid else if (key < a[mid]): hi = mid - 1 else: low = mid + 1 return -1

34. IBS - Efficiency From the above algorithm, we can determine that the running time is: T(n) = T(n/2) + O(1) = O(log n) Best Case : The output is obtained in a single run, i.e., O(1) , when the key is located at the middle of the array. Worst Case : The output is found at either end of the array, and the running time is O(log n) , as the array is halved with each step. Average Case : The running time is also O(log n) since, on average, the search will proceed through half of the array before finding the key. Unsuccessful Search : In the case of an unsuccessful search, the best, worst, and average time complexity remains O(log n) , as the algorithm will still halve the search space at each step until completion.

35. Application of Search Algorithms Search Engines : Efficient data retrieval from vast databases. Online Enquiry Systems : Finding user-specific data quickly. Text Pattern Matching : Searching for specific patterns or keywords. Spell Checker : Verifying word correctness by searching through a dictionary. Ant Algorithms : Used in optimization problems that involve searching large solution spaces.

36. Comparison of Sequential and Binary Search Algorithms Aspect Sequential Search Binary Search Time Complexity O(n) O(log⁡ n) Elimination per Comparison Eliminates only one element at a time from the search space Eliminates half of the remaining elements at each comparison Efficiency with Large Datasets As the number of elements nnn increases, the search requires significantly more work As nnn increases, the search requires much less work compared to sequential search Sorted Input Requirement Does not require elements to be in sorted order Requires elements to be in sorted order Ease of Implementation Simple to program but takes more time as the dataset grows Also simple to program but significantly faster in execution

37. Comparison of Search Methods Relationship Between List Search and Search Algorithms Foundation : List search provides the basis for understanding how elements can be located within a dataset. It encapsulates both sequential and binary searches, each tailored to different data arrangements. Sequential vs. Binary: Sequential Search : Best suited for small or unsorted lists due to its simplicity and ease of implementation. However, its performance degrades as the list size increases. Binary Search : Ideal for large, sorted datasets as it dramatically reduces the number of comparisons needed, making it much more efficient than sequential search.

38. Thank You ! A Presentation by Rakshit Dogra.

39. References and Resources Knuth, Donald E. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 1998. Cormen, Thomas H., et al. Introduction to Algorithms. MIT Press, 2009. Lamichhane, Ashim. Searching Algorithm - Data Structure and Algorithm Weiss, Mark Allen. Data Structures and Algorithm Analysis in C++. Pearson, 2014. Graphics: Hand Drawn