One of the most common ways of performing a search is to compare each item with the one we are looking for. This is known as linear search or sequential search. It is the most basic way of performing a search. If we consider that we have n items in a list, in the worst case, we have to search n items to find a particular item. We can iterate through a list or array to find an item. Let's consider the following example:

function search(array $numbers, int $needle): bool {
    $totalItems = count($numbers);

    for ($i = 0; $i < $totalItems; $i++) {
      if($numbers[$i] === $needle){
        return TRUE;
      }
     }
    return FALSE;
}

We have a function named search, which takes two arguments. One is the list of numbers, and the other is the number we are looking for in the list. We are running a for loop to iterate through each item in the list and compare them with our item. If a match is found, we return true and do not continue with the search. However, if the loop ends and nothing is found, we return false at the end of the function definition. Let's use the search function to find something using the following program:

$numbers = range(1, 200, 5); 

if (search($numbers, 31)) { 
    echo "Found"; 
} else { 
    echo "Not found"; 
}

Here, we are generating a random array using PHP's built-in function range, with a range of 1 to 200 inclusive. Each item will have a gap of 5 like 1, 6, 11, 16, and so on; then we are searching 31, which is in the list as we have 6, 11, 16, 21, 26, 31, and so on. However, if we want to search for 32 or 33, then the item will not be found. So, for this case, our output will be Found.

One thing we need to remember here is that we are not worried about whether our list is in any particular order or organized in a certain way. If the item we are looking for is in the first position, that will be the best result. The worst result can be the last item or an item that is not in the list. In both cases, we have to iterate over all n items of the list. Here is the complexity for linear/sequential search:

As we can see, the average or worst time complexity for a linear search is O(n), and that does not change how we order the list of items. Now, if the items in the array are sorted in a particular order, then we might not have to do a linear search, and we can get a better result by doing a selective or calculative search. The most popular and well-known search algorithm is "binary search". Yes, it sounds like the binary search tree you learned in Chapter 6, Understanding and Implementing Trees, but we can use this algorithm without even constructing a binary search tree. So, let's explore this.