Linear & Binary Search in DSA

Linear search:

Algorithm:

1. Start at the beginning: Start your search from the first item in the list.
2. ** Comparison:** Compare each element sequentially with the target.
3. Matching found: If a match is found, return the index.
4. No Match

Pseudocode:

function linearSearch(arr, target):
    for i from 0 to length(arr)-1:
        if arr[i] equals target:
            return i
    return -1

Real life example:

Consider looking for specific items in your shopping bag. You go through each item until you find what you're looking for.

Asymptotic Notation:

• Time complexity: O(n) (linear time complexity)

Use judgment and opinion:

• Suitable for small databases or unordered lists.
• Simplicity and ease of implementation make it a good choice for basic research requirements.
• Linear search is important when the data is not sorted in any order.

Binary search:

Algorithm:

1. Organize the list: Make sure the list is organized before starting the search.
2. Define pointers: Set pointers low and high to the beginning and end of the list.
3. Average calculation: Calculate the average of the current search area.
4. Comparison: Return the pointer if the middle element is the same as the target.
5. Adjust the pointers: If the target is less than the middle element, repeat the process in the left half; otherwise, repeat on the right half.
6. Repeat: Continue until the target is found or the pointer converges.

Pseudocode:

binary search function (ar, target):
    organize
    below = 0
    height = length (ar) - 1
    if low == high:
        average = (low + high) / 2
        if ar [middle] is equal to target:
            back to the middle
        else ar [middle] <target:
            low = medium + 1
        other
            high = medium - 1
    return -1

Real life example:

Consider looking up specific words in an organized dictionary. You open the book in the middle, determine whether the word is in the first half or the second, and repeat until you find the word.

Asymptotic Notation:

• Time complexity: O(log n) (logarithmic time complexity)

Use Cases and Considerations:

• Very efficient for large databases, especially when the data is ordered.
• Binary search does not apply to unstructured data because it depends on the ability to partition the search space.

The results:

Understanding the nuances of linear and binary search allows you to choose the right algorithm based on the characteristics of your data and the specific requirements of your search operation. Simplicity and versatility (linear search) or efficiency and structured data (binary search) are the most important, this algorithm offers a valuable tool for searching data in various scenarios.