Searching in Data Structure(Linear search and Binary search)

BCA

1. Lecture by: Ms Surbhi Saroha Centre for Distance and Online Education Shobhit Institute of Engineering & Technology [ NAAC “A” Grade Accredited, Deemed to be University ] Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

2. Syllabus Searching techniques , linear search binary search Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

3. Searching techniques Searching is the process of finding a particular item in a collection of items. A search typically answers whether the item is present in the collection or not. Searching requires a key field such as name, ID, code which is related to the target item. When the key field of a target item is found, a pointer to the target item is returned. The pointer may be an address, an index into a vector or array, or some other indication of where to find the target. If a matching key field isn’t found, the user is informed. Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

4. linear search Linear Search Algorithm is the simplest search algorithm. In this search  algorithm a sequential search is made over all the items one by one to search for the targeted item. Each item is checked in sequence until the match is found. If the match is found, particular item is returned otherwise the search continues till the end. Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

5. Algorithm LinearSearch ( Array A, Value x) Step 1: Set i to 1 Step 2: if i > n then go to step 7 Step 3: if A[ i ] = x then go to step 6 Step 4: Set i to i + 1 Step 5: Go to Step 2 Step 6: Print Element x Found at index i and go to step 8 Step 7: Print element not found Step 8: Exit Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

6. Linear Search complexity Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University) Case Time Complexity Best Case O(1) Average Case O(n) Worst Case O(n)

7. Binary Search Algorithm Binary Search Algorithm is fast according to run time complexity. This algorithm works on the basis of divide and conquer rule. In this algorithm we have to sort the data collection in ascending order first then search for the targeted item by comparing the middle most item of the collection. If match found, the index of item is returned. If the middle item is greater than the targeted item, the item is searched in the sub-array to the left of the middle item. Otherwise , the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the sub array reduces to zero. Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

8. Algorithm Step 1: Data list must be ordered list in ascending order. Step 2: Probe middle of list Step 3: If target equals list[mid], FOUND. Step 4: If target < list[mid], discard 1/2 of list between list[mid] and list[last]. Step 5: If target > list[mid], discard 1/2 of list between list[first] and list[mid]. Step 6: Continue searching the shortened list until either the target is found, or there are no elements to probe. Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

9. Complexity Analysis of Binary Search: Time Complexity:   Best Case: O(1) Average Case: O(log N) Worst Case: O(log N) Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

10. Advantages of Binary Search: Binary search is faster than linear search, especially for large arrays. More efficient than other searching algorithms with a similar time complexity, such as interpolation search or exponential search. Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive or in the cloud. Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

11. Drawbacks of Binary Search: The array should be sorted. Binary search requires that the data structure being searched be stored in contiguous memory locations.  Binary search requires that the elements of the array be comparable, meaning that they must be able to be ordered. Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)

12. THANK YOU  Shobhit Institute of Engineering and Technology (NAAC 'A' Grade Deemed to be University)