Sure, let's define a Binary Search function which is the classical example of a function with a time complexity of O(log n).
A binary search algorithm works by continuously dividing the list in half until the desired value is found, or all elements have been checked. "n" signifies the number of elements in the list. The O(log n) time complexity notation indicates that the time it takes to run the algorithm increases logarithmically with the size of the input: it will not double the time every time we double the number of elements.
Here's the step-by-step explanation:
1. Define the function binary search, which takes an array and a target element as input.
2. Set two pointers, "left" and "right" at the start and end of the array respectively.
3. Enter a loop that continues until "left" is less than or equal to "right":
- Calculate the middle index by taking the average of "left" and "right", and performing integer division to avoid decimal points.
- Check if the middle element at the calculated index matches the target element:
- If it is a match, return the middle index.
- If the middle element is less than the target, move the "left" pointer to one position after the "middle" index, effectively reducing the search space to the right half of the array.
- If the middle element is greater than the target, move the "right" pointer to one position before the "middle" index, effectively reducing the search space to the left half of the array.
4. If the loop completes without finding a match, return -1 to indicate that the element was not found in the array.
The beauty of the binary search algorithm lies in its efficient time complexity of O(log(n)). As the size of the input increases, the time taken to find an element doesn't increase linearly (as would be the case in a simple linear search), but rather logarithmically, thus making it an excellent choice for searching in large, sorted data sets.