A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. It is widely used in computer science for efficient data storage, retrieval, and manipulation.

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. It is widely used in computer science for efficient data storage, retrieval, and manipulation.

1. Searching Algorithms

2. Searchng Techniques There are two types of searching techniques Linear Search Binary Search

3. Linear Search

4. Introduction Linear search is a simple search algorithm that sequentially checks each element in a list until a match is found or the end of the list is reached. Key Characteristics Simplicity Unsorted List Deterministic Flexibility Sequential Nature

5. Algorithm The linear search algorithm involves the following steps: Start from the first element of the list. Compare the current element with the target value. If the element matches the target, return its index. If the end of the list is reached without finding a match, return a not-found indication.

6. Pseudo Code linearSearch (a, n, val ) {        for  ( i  = 0;  i  < n;  i ++)       {            if  (a[ i ] ==  val )            return  i+1;       }      return  -1;   }  

7. Recursive Pseudo code LinearSearch (array, index, key):     if index < 0:         return -1;     if item = key:         return index     return LinearSearch (array, index-1, key)

8. Example – When key is present in the array

9. Example – When key is not present in the array

10. Time Complexity The time complexity of linear search is O(n), where n is the number of elements in the list. In the worst-case scenario, when the target is not present or is located at the end of the list, the algorithm may need to check each element in the list before finding a match. Best Case: O(1) Average Case: O(n/2) Worst Case: O(n)

11. Advantages & Limitations Simplicity: Linear search is easy to understand and implement. Applicability: It can be used on both sorted and unsorted lists. Versatility: It can be used with various data types, not just numeric values. It can search for characters, strings, objects, or any other data types. Memory Efficiency: It doesn't require any additional data structures or memory overhead. It can be performed with minimal memory usage. Time Complexity: It has an average and worst-case time complexity of O(n). The time taken to perform the search increases linearly. For large lists, this can result in slow performance. Performance: It is not the best choice for sorted lists where binary search or other efficient algorithms are available.

12. Conclusion Linear search is a straightforward algorithm for searching elements in a list. However, its efficiency decreases as the size of the list grows, making it less suitable for large-scale applications. Other search algorithms, such as binary search, offer faster search times for sorted lists.

13. Binary Search Searching Algorithm

14. Introduction Binary Search is one of the fastest searching algorithms. It is used for finding the location of an element in a linear array. It works on the principle of divide and conquer technique. Binary Search Algorithm can be applied only on  Sorted arrays . So, the elements must be arranged in- Ascending order if the elements are numbers. Or dictionary order if the elements are strings. To apply binary search on an unsorted array, First, sort the array using some sorting technique. Then, use binary search algorithm.

15. Algorithm There is a linear array ‘a’ of size ‘n’. Binary search algorithm is being used to search an element ‘item’ in this linear array. If search ends in success, it sets loc to the index of the element otherwise it sets loc to -1. Variables beg and end keeps track of the index of the first and last element of the array or sub array in which the element is being searched at that instant. Variable mid keeps track of the index of the middle element of that array or sub array in which the element is being searched at that instant.

16. Pseudo Code Begin Set beg = 0 Set end = n-1 Set mid = (beg + end ) / 2 while ( (beg <= end ) and (a[mid] ≠ item) ) do if (item < a[mid]) then Set end = mid - 1 else Set beg = mid + 1 endif Set mid = (beg + end ) / 2 endwhile if (beg > end ) then Set loc = -1 else Set loc = mid endif End

17. Recursive Pseudo Code binarySearch(A, low, high, x) { if (low > high) { return -1; } mid = (low + high) / 2; if (x == A[mid]) { return mid; } else if (x < A[mid]) { return binarySearch(A, low, mid - 1, x); } else { return binarySearch(A, mid + 1, high, x); } }

18. Example

19. Time Complexity The time complexity of a binary search algorithm is O(log n), where 'n' is the number of elements in the sorted array. This makes binary search one of the most efficient search algorithms for sorted data. Binary search follows a divide-and-conquer approach and repeatedly divides the search space in half, discarding one half based on the comparison of the middle element with the target element. By eliminating half of the remaining elements at each step, binary search quickly reduces the search space to a small fraction of the original size. Best Case: O(1) Average Case: O(logn) Worst Case: O(logn)

20. Advantages Efficiency: It is highly efficient, especially for large sorted data sets, as it drastically reduces the search space with each iteration. Optimal Use of Sorted Data: It requires the data to be sorted, but it takes full advantage of this property. It efficiently narrows down the search range by comparing with the middle element, resulting in faster search times. Versatility: It can be applied to a wide range of applications, such as searching in databases, finding elements in sorted arrays, and implementing search features in algorithms and data structures. Fewer Comparisons: In comparison to linear search, binary search typically requires fewer comparisons to find the target value, making it more efficient, especially for large data sets. Consistent Performance: Binary search consistently performs well on sorted data, regardless of the size of the list or array, offering reliable and predictable search times.

21. Limitations Sorted Data Requirement: It requires the input data to be sorted in ascending or descending order. If the data is not already sorted, it must be sorted first, which can add extra time and memory overhead. Limited Applicability: Binary search is only applicable to sorted data sets. It is not suitable for unsorted data or data with dynamic changes. Memory Overhead: Binary search requires random access to elements, which is straightforward with arrays. Inefficient for Dynamic Data: If the data set frequently changes, re-sorting the data each time is impractical. Other search algorithms or data structures like hash tables may be better suited for dynamic data. Performance with Duplicates: Binary search may not always return the first or last occurrence of a duplicate value in the list. Depending on the specific implementation, it may return any of the duplicates found.

22. Conclusion In conclusion, binary search is a powerful and efficient searching algorithm that dramatically reduces search time through its divide-and-conquer strategy. It is highly suitable for large sorted data sets, providing a logarithmic time complexity for searching operations. With its wide range of applications and ability to optimize search processes, binary search remains a fundamental tool in computer science and data processing.