Consider the following image. We have an array with repetitive items. If we try to find the first appearance of 2 from the array, binary search algorithm from the last section will give us the fifth element. However, from the following image, we can see clearly it is not the fifth element; instead, it is the second element, which is the correct answer. So, a modification is required in our binary search algorithm. The modification will be a repetitive searching until we reach the first appearance:

Here is the modified solution using iterative approach:

function repetitiveBinarySearch(array $numbers, int $needle): int { 
    $low = 0;
    $high = count($numbers) - 1;
    $firstOccurrence = -1;

    while ($low <= $high) { 
      $mid = (int) (($low + $high) / 2); 

      if ($numbers[$mid] === $needle) { 
          $firstOccurrence = $mid; 
          $high = $mid - 1; 
      } else if ($numbers[$mid] > $needle) { 
          $high = $mid - 1;
      } else {
          $low = $mid + 1;
      } 
    } 
    return $firstOccurrence; 
} 

As we can see, first we are checking whether the mid has the value we are looking for. If it is true, then we are assigning the middle index as first occurrence, and we will search the left of the middle element to check for any occurrences of the number we are looking for. We then continue the iteration until we have searched each index ($low is greater than $high). If no further occurrence is found, then the variable first occurrence will have the value of the first index where we found the item. If not, we are returning -1 as usual. Let's run the following code to check whether our results are correct or not:

$numbers = [1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5]; 

$number = 2; 

$pos = repetitiveBinarySearch($numbers, $number); 

if ($pos >= 0) { 
    echo "$number Found at position $pos 
"; 
} else { 
    echo "$number Not found 
"; 
} 

$number = 5; 
$pos = repetitiveBinarySearch($numbers, $number); 

if ($pos >= 0) { 
    echo "$number Found at position $pos 
"; 
} else { 
    echo "$number Not found 
"; 
}

Now, we have an array with repetitive values of 2, 3, 4, and 5. We want to search the array and find the position or index where the value has appeared for the first time. For example, if we are searching 2 in a regular binary search function, it will return eighth as the position where it found the value 2. In our case, we are actually looking for the second index, which actually holds the first appearance of item 2. Our function repetitiveBinarySearch does exactly that, and we are storing the return position to a variable called $pos. We are showing the output if the number is found along with the position. Now, if we run the preceding code in our console, we will have the following output:

2 Found at position 1
5 Found at position 16

This matches our expected results. So, we can say we now have a repetitive binary search algorithm to find first and last occurrences of an item from a given sorted list. This might be a very handy function to solve many problems.

So far, from our examples and analysis, we can conclude that binary searching is definitely faster than linear searching. However, the major prerequisite is to have the list sorted before applying binary search. Applying binary search in an unsorted array will lead us to inaccurate results. There can be situations where we receive an array and we are not sure whether the array is sorted or not. Now, the question is, "Should we sort the array first and apply binary search algorithm in such cases? Or should we just run a linear search algorithm to find an item?" Let's discuss this a little, so that we know how to handle such situations.