Question 7: Given the sorted array A: #(11 15 24 25 27 35 39 42 54 62 64 67 77 81 94) a. Use binary search to find a = 39 in the array. In your answer, you must show the sub-array elements considered for the search in each pass of the algorithm. b. Explain and express the time complexity of the binary search in terms of the size of the input. At last, show this time complexity with big O notation.
(Q7) This is a Data Structures problem and the
The Common Lisp program you provided is a binary search algorithm implementation:
The
binary-searchfunction takes two arguments:array(a sorted array to search in) andtarget(the element to find).It initializes two variables,
leftandright, which represent the left and right indices of the current search range.leftis initially set to 0, andrightis set to the index of the last element in the array (the length of the array minus 1).The program enters a loop that continues until the
leftindex is greater than therightindex. This loop is the core of the binary search algorithm.Inside the loop, it calculates the
midindex, which represents the middle of the current search range. Themidindex is computed as the integer result of averaging theleftandrightindices.The algorithm checks if the element at the
midindex in the array matches thetarget. If it does, the function returnsmid, indicating that the target element has been found.If the element at the
midindex is less than thetarget, it means that the target must be in the right half of the remaining search space. In this case, it updates theleftindex tomid + 1.If the element at the
midindex is greater than thetarget, it means that the target must be in the left half of the remaining search space. In this case, it updates therightindex tomid - 1.If the loop exits without finding the target (when
leftbecomes greater thanright), the function returnsnil, indicating that the target element is not in the array.In the example usage section, a sorted array
sorted-arrayand a target elementtarget(in this case, 39) are defined. Thebinary-searchfunction is called with these arguments, and the result is stored in theresultvariable.Finally, the program prints a message to the console using
format t. If the result is notnil, it indicates that the target was found, along with the target element and its index in the array. If the result isnil, it indicates that the target was not found in the array.
Step by step
Solved in 7 steps with 3 images
