Algorithms: Search

Question 1

Binary Search

Answer 1

Binary search is used to find a specified value in a sorted list of items (or if it does not occur in the list, to determine that fact). The idea is to test the element in the middle of the list. If that element is equal to the specified value, you are done. If the specified value is less than the middle element of the list, then you should search for the value in the first half of the list. Otherwise, you should search for the value in the second half of the list. The method used to search for the value in the first or second half of the list is a binary search. That is, you look at the middle element in the half of the list that is still under consideration, and either you’ve found the value you are looking for, or you have to apply binary search to one-half of the remaining elements. And so on!

Question 2

Pre conditions for Binary Search

Answer 2

Array connot be empty and must be sorted in increasing order