Design and write a binary search function that searches for a value in a sorted integer array of size
1000.

Question

Design and write a binary search function that searches for a value in a sorted integer array of size 
1000.

Accepted Answer

```python # define a binary search function def binary_search(arr, target): # initialize the starting index to 0 left = 0 # initialize the ending index to the length of the array minus one right = len(arr) - 1 # use a while loop to iterate until the starting index is less than or equal to the ending index while left <= right: # calculate the middle index mid = (left + right) // 2 # if the target is found at the middle index, return the index if arr[mid] == target: return mid # if the target is smaller than the middle element, adjust the ending index elif arr[mid] > target: right = mid - 1 # if the target is larger than the middle element, adjust the starting index else: left = mid + 1 # if the target is not found in the array, return -1 return -1 ``` ```python # main function that tests binary_search function def main(): # create a sorted array of size 1000 arr = list(range(1000)) # test the binary_search function with a value that exists in the array assert binary_search(arr, 500) == 500 # test the binary_search function with a value that does not exist in the array assert binary_search(arr, 1001) == -1 # call the main function to execute the tests main() ``` ∻Explanation∻ ⚹The binary search function takes a sorted array and a target value as inputs. It initializes two pointers to the start and end of the array and iteratively adjusts these pointers to find the target value. If the target is found, it returns the index; otherwise, it returns -1. The main function tests the binary search function with two use cases: one where the target value is in the array and one where it is not.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Define the binary search function that takes a sorted array and a target value as arguments. ‖ ‖ ▪ ⋮ Initialize two pointers, left and right, to the start and end of the array, respectively. ‖ ‖ ▪ ⋮ Use a while loop to iterate as long as left is less than or equal to right. ‖ ‖ ▪ ⋮ Calculate the middle index using the formula $mid = \frac{left + right}{2}$. ‖ ‖ ▪ ⋮ Compare the target value with the middle element of the array and adjust pointers accordingly. ‖ ‖ ▪ ⋮ Return the index of the target if found, otherwise return -1. ‖ ‖ ▪ ⋮ Define the main function to test the binary search function with concrete use cases. ‖ ‖ ▪ ⋮ Call the main function to execute the tests. ‖ ∻Time Complexity∻ ⚹The time complexity of binary search is $O(\log n)$ because the search space is halved with each iteration.⚹ ∻Space Complexity∻ ⚹The space complexity is $O(1)$ as it only uses a constant amount of extra space.⚹

Sia