Introduction

Finding the lowest index of a given value in a presorted array is a common problem in computer science. Presorted arrays offer a unique advantage for search operations due to their orderly structure. This article explores the techniques used to solve this problem, with an emphasis on binary search algorithms and their complexities. We'll also look at practical examples and discuss some edge cases.

Searching for the Lowest Index

Binary Search Overview

The binary search algorithm is a powerful technique to efficiently search for a value within a sorted array. It drastically reduces the time complexity of a search operation from linear to logarithmic time, making it well-suited for large datasets. The algorithm works by repeatedly dividing the search interval in half:

1. Initialization: Start with the entire array. Set two pointers, `low` and `high`, at the start and end of the array, respectively.
2. Midpoint Calculation: Calculate the midpoint of the current interval.
3. Comparison and Feedback: Compare the midpoint's value with the target value:
   • If they are equal, check if this is the first occurrence of the value.
   • If the target value is less, narrow the interval to the left half by moving the `high` pointer to `mid - 1`.
   • If the target value is greater, narrow the interval to the right half by moving the `low` pointer to `mid + 1`.
4. Repetition: Repeat steps 2 and 3 until the pointers converge or the target is found.

Finding the Lowest Index

To adapt binary search to find the lowest index of a given value, an additional check is introduced when a match is found. Instead of immediately returning the index, the algorithm verifies if the preceding element is different. This additional check ensures the discovery of the first occurrence:

• Early Termination: If the first occurrence is found (`mid` is zero or the element just before `mid` is different from the target), return `mid` as the result.
• Continue Search on Left Half: If a match is found, but it's not the first occurrence, continue searching the left half by moving `high` to `mid - 1`.

Implementation

Here's a simple implementation in Python: