C++ Search Algorithms (CSA)

AVAILABLE:    5

1. Sequential Search
   Sequential Search is the simplest method but also the least efficient. This method operates slower compared to others but is the most likely to be applied to unsorted arrays.

Algorithm (pseudocode)

bool found;
int i = 0;
found = false;
while (i < 10 || !found) {
    if (search == array[i]) {
        found = true;
        position = i;
    }
    i++;
}

1. Search in Sorted Arrays
   Searching is done by comparing the first element. If the array is sorted in ascending order, the search will continue as long as the target data is smaller than the current array element. If the array element becomes greater than the target, the search can stop because the target data is definitely not present.

Algorithm (pseudocode)

bool found;
int i = 0;
found = false;
do {
    if (search == array[i]) {
        found = true;
        position = i;
    }
    i++;
} while ((i < 10) || (!found) || (search < array[i]));

1. Binary Search
   Binary Search can only be used on sorted arrays. Here’s how binary search works:

   | 1 | 5 | 6 | 10 | 11 | 12 | 32 | 34 | 56 | 99 |
   

   Suppose we are searching for the position of 56. First, divide the array into two subarrays:

   | 1           | 5 | 6 | 10 | 11 |   | 12          | 32 | 34 | 56 | 99 |
   |-------------|---|---|----|----|---|-------------|----|----|----|----|
   | Subarray 1  |   |   |    |    |   | Subarray 2  |    |    |    |    |
   

   Compare 56 with the last element of Subarray 1 (11). If 56 is smaller than 11, it will be searched in Subarray 1. Otherwise, it will be searched in Subarray 2. The same process is repeated for Subarray 2, which is divided further:

   | 12            | 32 | 34 |   | 56            | 99 |
   |---------------|----|----|---|---------------|----|
   | Subarray 2.1  |    |    |   | Subarray 2.2  |    |
   

   Comparing 56 with the last element of Subarray 2.1 (34), since 56 is larger, the search continues in Subarray 2.2. The process is repeated until the target data is found.
   

   With 4 iterations, the data can be located.

Algorithm (pseudocode)

bool found;
int upper, middle, lower;
found = false;
lower = 0;
upper = 10;
while ((lower < upper) || !found) {
    middle = (upper + lower) / 2;
    if (search < array[middle]) {
        upper = middle - 1;
    } else if (search > array[middle]) {
        lower = middle + 1;
    } else if (search == array[middle]) {
        found = true;
        position = middle;
        lower = upper + 1;
    }
}

Source

Course: Data Structures, STMIK EL Rahma Yogyakarta.
Compiled by: Eko Riswanto.