Consider an array of size 512. If you want to search for a particular data, How many comparisons will be required there in case of worst case? Consider both linear and binary search.
Answers
Answer:
your answer is here
Explanation:
First things first. Note that binary search can be done only in a sorted array.
The worst case of a binary search is when you search for the first element or the last element in the array or search for an element which does not exist in the array and is lower than the first element in the array or higher than the last element in the array. This is because we always compare the element we search with the middle element in any range.
The accurate no. of comaparisons depends on how you implement your binary search. But it is appx. equal to log2(1000) which is appx. 10 comparisons. It could be 11 or 12 comparisons if your implementation checks for array boundaries. To calculate it accurately you can do a comparison++ wherever you do a comparison in your implementation.