**Course Title:** Mastering C: From Fundamentals to Advanced Programming **Section Title:** Sorting and Searching Algorithms **Topic:** Searching algorithms: linear search and binary search **Objective:** By the end of this topic, you will be able to: 1. Explain the linear search algorithm and its applications. 2. Implement linear search in C programming language. 3. Describe the binary search algorithm and its advantages. 4. Implement binary search in C programming language. 5. Compare and contrast linear search and binary search algorithms. **Searching Algorithms:** In computer science, searching is the process of finding a specific value within a collection of data. There are several searching algorithms, and we will be covering two of the most commonly used algorithms: linear search and binary search. ### Linear Search **Linear Search Algorithm:** Linear search, also known as sequential search, is a basic searching algorithm that works by comparing each element in the collection with the desired value until a match is found. The algorithm starts at the beginning of the collection and continues until the end, checking each element individually. **Example:** Suppose we have an array of integers `arr = [2, 4, 6, 8, 10]`, and we want to find the value `6`. ``` int arr[] = {2, 4, 6, 8, 10}; int target = 6; int length = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < length; i++) { if (arr[i] == target) { printf("Found at index %d\n", i); return 0; // exit the program } } ``` **Time Complexity:** The time complexity of linear search is O(n), where n is the number of elements in the collection. This means the time taken to search for an element increases linearly with the size of the collection. ### Binary Search **Binary Search Algorithm:** Binary search is an efficient searching algorithm that works by dividing the collection in half and repeatedly narrowing down the search interval until the desired value is found. The algorithm requires the collection to be sorted in ascending or descending order. **Example:** Suppose we have an array of integers `arr = [2, 4, 6, 8, 10]`, and we want to find the value `6`. ``` int arr[] = {2, 4, 6, 8, 10}; int target = 6; int length = sizeof(arr) / sizeof(arr[0]); int left = 0; int right = length - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) { printf("Found at index %d\n", mid); return 0; // exit the program } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } ``` **Time Complexity:** The time complexity of binary search is O(log2(n)), where n is the number of elements in the collection. This means the time taken to search for an element decreases logarithmically with the size of the collection. **Comparison and Contrast:** | Algorithm | Time Complexity | Advantages | Disadvantages | | --- | --- | --- | --- | | Linear Search | O(n) | Simple to implement, works on unsorted collections | Slow for large collections | | Binary Search | O(log2(n)) | Fast for large collections, efficient | Requires sorted collection, more complex to implement | **Practice:** Implement both linear search and binary search algorithms using the given examples as a starting point. Test the algorithms with different collections and targets. **External Resources:** For additional practice and reference, visit: * GeeksforGeeks: [Linear Search](https://www.geeksforgeeks.org/linear-search/) and [Binary Search](https://www.geeksforgeeks.org/binary-search/) * Wikipedia: [Linear Search](https://en.wikipedia.org/wiki/Linear_search) and [Binary Search](https://en.wikipedia.org/wiki/Binary_search) **Leave a Comment/Ask for Help:** If you have any questions or would like to discuss the topic further, please leave a comment below. **Next Topic:** In the next topic, we will cover [Analyzing algorithm efficiency: Big O notation.](link)