Can you please give me a theoretical representation of these questions: do you a
ID: 3841394 • Letter: C
Question
Can you please give me a theoretical representation of these questions:
do you actually agree with the theoretical representation of the results presented to you? How would you go about proving or disproving what you have been told about the order of algorithms in relation to reality?
a. Create an ordered array list with 100 random items in it and then perform a binary search on the array list looking for an item that is present in the list. Count the number of comparisons required to find the item in the list.
b. Do the same problem as part an again, but this time look for an item that is not in the list.
Thanks
Explanation / Answer
Create an array with 100 items
For each item give a random value
Initialize count to 0
Apply binary search technique to find if the value x is present
[Binary Search
Take the middle value and compare with x
If x is lesser, then consider the first half of the array and increment count by 1
If x is higher, then consider the second half of the array and increment count by 1
If x is equal, then return count
]
Binary search works on Sorted lists only. We are not sure that the random list we are having is of sorted items.
a) When we are checking middle element, we are not sure that the elements before it are lesser. Then there is no way that it is going to be found.
b) When list is not sorted, we are not sure about binary search technique being applied on it. We are not conisdering the items, which we need to in this case and checking arbitary numbers and returning that it is not found.