Searching and Sorting Algorithms Review

## Searching Algorithms Searching algorithms let you search for a target within a certain list of items. In computer science, there are two searching algorithms you should know about. They are **linear search** and **binary search** algorithms. It is important to understand the differences between the two algorithms and when to use each one. ### Linear Search - Linear search iterates through an array of items, checking each item from the beginning until the target item is found. - If the target item is found, the index where it is located in the array is returned. - If the target is not found, it returns `-1`, which means **invalid index** in JavaScript. - Because linear search checks each item until it finds the target, it is not efficient for a large array of items. - The time complexity of linear search is `O(n)` because the time it takes to search through the array grows linearly with the size of the array. - The space complexity of linear search is `O(1)` because it doesn't require any additional space to search through the array. ### Binary Search - Binary search works by dividing an array of items in half, and checking if the target value is in the middle of the array. - The condition for binary search to work is that the items in the array must be sorted, either in ascending or descending order. - Binary search is a more efficient algorithm for searching through a large array of items because it divides the array in half and ignores any half where the target is not found. - If the target item is found in the middle of the array, the index of the target item is returned. - If the item is not found, the algorithm checks if the target item is in the left or right half of the array. - It continues to divide the remaining parts of the array into halves until the target item is found. - If the target item is not found in the array, it returns `-1`, - The time complexity of binary search is `O(log n)` because the time it takes to search through the array grows logarithmically with the size of the array. - The space complexity of binary search is `O(1)` because it doesn't require any additional space to search through the array. ### How Linear Search Differs from Binary Search - Binary search is more suitable for a large array of items compared to linear search. - The time complexity of linear search is `O(n)` because the time it takes to search through the array grows linearly with the size of the array. - The time complexity of binary search is `O(log n)` because the time it takes to search through the array grows logarithmically with the size of the array. ## Sorting Algorithms and Divide-and-Conquer In computer science, divide-and-conquer is a technique used to break down a problem into smaller sub-problems so they are easier to solve. Recursion is the technique often employed in divide-and-conquer, and divide-and-conquer is a powerful strategy used to implement many efficient sorting algorithms like merge sort. ### Merge Sort - Merge sort is a sorting algorithm that follows the divide-and-conquer approach. - It works by recursively dividing an array into smaller sub-arrays until each sub-array contains only one element. - It then repeatedly merges the sub-arrays back together in a sorted order. - The time complexity for merge sort is `O(n log n)` because the array is continuously divided in half `(log n)` and then merged together `(O(n))`. - The space complexity of merge sort is `O(n)` because it is not an in-place sorting algorithm.