Searching for a value

Linear/Sequential Search

PSEUDOCODE

Let L represent an array of values
    Let n represent the size of the array
Let T represnet target value T, 
Let i represent index of L

1. Set i to 0.
2. If L[i] = T, the search terminates successfully; return i.
3. If i < n, Increase i by 1 and go to step 2. 
4. If i == n, the search terminates unsuccessfully.

Linear Search is the act of looking through a collection from the start and determining the index of the value you are searching for.

• Best Case Scenario: The first item is the target value

• Average Case: The target is somewhere near the middle of the dataset

• Worst Case: The target is not found, and you have analyzed every single value

By encountering the worst case scenario, we can potentially have a slow algorithm.

If the array had a million data points, and our target value is not one of the given value, the algorithm would be required to make a million comparisons to determine it is not in the array.

The study of efficiency of algorithm is called Complexity Analysis.

The search algorithm is called "linear" because it individually searches for the target from start to end.

Binary Search

PSEUDOCODE

Let A represent a sorted array of values
    Let n represent the size of A
Let L represent left index point
Let R represent right index point
Let m represent middle index point
Let T represent the target value of interest

1.  L = 0
2.  R = n − 1
3.  while L <= R do:
4.      m := floor((L + R) / 2)
5.      if A[m] < T then
6.          L := m + 1
7.      else if A[m] > T then
8.          R := m − 1
9.      else:
10.         return m
11. return unsuccessful

Binary Search is a searching algorithm that works only on sorted and comparable dataset. It is considered to be significantly faster than linear search because it ignores where the target value cannot exist in the dataset by comparing the target with its generated midpoint.

The midpoint changes every iteration to shrink the search range within the dataset until the target is found or not found.

Linear vs Binary Search

Let A be a list of integers from 1 to 100 inclusively.
Let T be a value of 77

LinearSearch(A, T) would do 77 comparisons to determine that 77 exists at index 76

BinarySearch(A, T) would do the following comparisons:
Comparison 1 -> Is T a value of 50? (No) ... 50 = (1 + 100) / 2 rounded down
Comparison 2 -> Is T > 50? (Yes)
    - At this point our search range was updated to 51 to 100 rather than 1 to 100

Comparison 3 -> Is T a value of 75? (No)
Comparison 4 -> Is T > 75? (Yes)
    - At this point our search range is 76 to 100
    
Comparison 5 -> Is T a value of 88 (No)
Comparison 6 -> Is T > 88 (No)
    - At this point our search range is 76 to 88

Comparison 7 -> Is T a value of 81 (No)
Comparison 8 -> Is T > 81 (No)
    - At this point our search range is 76 to 81

Comparison 9 -> Is T a value of 78 (No)
Comparison 10 -> Is T > 78 (No)
    - At this point our search range is 76 to 78

Comparison 10 -> Is T a value of 77 (Yes)
    - The search is now completed

As the dataset gets bigger, the linear search will do more comparisons compared to binary search. This classifies that binary search is a faster algorithm than linear search.

The weakness of binary search are the following:

• The dataset must be sorted (which increases complexity if the dataset is not sorted)

• The dataset must be comparable

• The algorithm cannot be used to find multiple instances or duplicates; it can only generate a single answer

Connected Reading

• Linear Search (Link)
• Binary Search (Link)
• Big-O Notation (Link)