Implement a binary search algorithm in Python and explain its time complexity.
- User
Implement a binary search algorithm in Python and explain its time complexity.
Assistant
Binary search is a search algorithm that works by repeatedly dividing the search interval in half. It makes use of the divide and conquer strategy to search for a target value in a sorted array.
Here's the implementation of binary search in Python:
def binary_search(arr, target): left = 0 right = len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1In this implementation, we start by setting
leftandrightpointers to the bounds of the array. We then continue iterating while the left pointer is less than or equal to the right pointer. Inside the while loop, we calculate the middle indexmidand check if the target value is present at that index. If the target is found, we return the indexmid. If the target is less than the value atmid, we move the left pointer to the right ofmid. Otherwise, we move the right pointer to the left ofmid. If the while loop completes without finding the target, we return -1 to indicate that the target is not present in the array.The time complexity of binary search is O(log n), where n is the length of the array being searched. This is because in each iteration, we divide the search space by half, effectively reducing the remaining search space by a factor of 2. This leads to a logarithmic number of iterations required for finding the target, hence the O(log n) time complexity.
Note: Binary search is a very efficient search algorithm for arrays that are already sorted. However, it requires that the array is sorted in advance, which may not always be the case. In such scenarios, linear search might be a more appropriate search algorithm.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.