Question

Given a sorted array A of size n, we want to find if an element k belongs to this array. What will be the best time complexity to perform this search operation?

1) O(1)
2) O(log n)
3) O(n)
4) O(n²)

Answer 1

The best time complexity to perform a search operation on a sorted array is O(log n).

Step-by-step explanation:

The best time complexity to perform the search operation on a sorted array of size n to find if an element k belongs to the array is O(log n). This can be achieved by using a binary search algorithm, which recursively divides the array into halves until the desired element is found or the search range is exhausted. Compared to linear search (O(n)) or quadratic search (O(n²)), binary search has a much more efficient time complexity.