Linear and Binary search

Linear Search: = Linear search

• Definition: Linear search, also known as sequential search, is a simple searching algorithm that iterates through each element in a collection (e.g., array or list) sequentially until the target element is found or the end of the collection is reached.
• Algorithm: Starting from the beginning of the collection, each element is checked one by one until the target element is found or the end of the collection is reached.
• Complexity: Linear search has a time complexity of O(n), where n is the number of elements in the collection. This means the time taken to search grows linearly with the size of the collection.
• Suitability: Linear search is suitable for small collections or when the elements are not sorted. It's easy to implement and understand but may not be efficient for large collections.

Advantages:

1. Simplicity: Linear search is straightforward to implement and easy to understand. It involves iterating through each element sequentially.

2. Applicability: Linear search can be applied to both sorted and unsorted collections. It doesn't require any pre-processing of the data.

Disadvantages:

1. Efficiency: Linear search has a time complexity of O(n), meaning it may not be efficient for large collections. As the size of the collection grows, the time taken for searching increases linearly.

2. Performance: Linear search may not be suitable for searching in very large datasets or situations where fast retrieval is required, as it checks each element one by one.

1. Linear Search

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i + 1; // Return index of the found element (1-based indexing)
        }
    }
    return "not found";
}

Linear search iterates through the array sequentially until it finds the target element or reaches the end. It has a time complexity of O(n), where n is the number of elements in the array.

Binary Search:=Binary search

• Definition: Binary search is an efficient searching algorithm used to find the position of a target element in a sorted collection (e.g., array or list). It works by repeatedly dividing the search interval in half until the target element is found or the interval is empty.
• Algorithm: Binary search compares the target element with the middle element of the collection. If the target is less than the middle element, the search continues in the lower half of the collection; if it's greater, the search continues in the upper half. This process repeats until the target element is found or the interval is empty.
• Complexity: Binary search has a time complexity of O(log n), where n is the number of elements in the sorted collection. This means the time taken to search grows logarithmically with the size of the collection, making it significantly faster than linear search for large collections.
• Suitability: Binary search is highly efficient for searching in sorted collections. It's commonly used in scenarios where the data is sorted and requires fast retrieval, such as in searching algorithms, database operations, and more.

Advantages:

1. Efficiency: Binary search has a time complexity of O(log n), making it significantly faster than linear search for large collections. It's highly efficient, especially for sorted collections.

2. Fast Retrieval: Binary search quickly narrows down the search space by dividing the collection in half at each step, leading to faster retrieval of the target element.

Disadvantages:

1. Requirement of Sorted Data: Binary search requires the data to be sorted beforehand. If the data is not sorted, additional preprocessing steps are needed, which can add complexity and time.

2. Implementation Complexity: While the concept of binary search is straightforward, its implementation may be more complex compared to linear search, especially for beginners.
   

function binary(arr, target, start, end) {
    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        if (arr[mid] <= target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return start;
}

Binary search finds the position of a target element in a sorted array by repeatedly dividing the search interval in half. It has a time complexity of O(log n), where n is the number of elements in the array.

Conclusion

• Linear search is suitable for small arrays or unsorted arrays.
• Binary search is efficient for searching in sorted arrays.

Binary search

Linear search