How to write binary search algorithm?, Data Structure & Algorithms

Q. Write down the binary search algorithm and trace to search element 91 in following given list:

13          30          62           73         81         88             91

What are the major limitations of Binary Search?                                               

Ans.

13   30   62   73   88   91

lets us store the numbers in an array

2064_stack.png


To start with we take low = 0 and high = 5 hence mid = (low+high)/2 = (0+5) /2 = 2

since a[mid] = a[2] = 62 ≠ 91 and low < high we go to next iteration as 62 < 91

∴we take low = mid+1 = 3 and high =

now we find mid =( 3+5)/2 = 4

∴a [mid] = a[4] = 88.

88 is not equal to 91

again 88< 91

∴ we take low = mid +1 = 4 + 1 = 5 and high = 5

∴mid = (5+5)/2 = 5

∴ a[mid] = a[5] = 91 which is the search element.

Limitation of Binary Search is given below: -

(i) The complexity of Binary search is O(log2 n)  the complexity is same irrespective of the  location of the element, even if it is not there in the array.

(ii) The algorithm makes an assumption that one has direct access to middle element in the list on a sub list. This means that the list must be stored in some type of array. Unfortunately inserting an element in an array requires element to be moved down the list and deleting an element from an array requires element to be moved up the list.

(iii) The list must be sorted.

Posted Date: 7/13/2012 2:47:14 AM | Location : United States







Related Discussions:- How to write binary search algorithm?, Assignment Help, Ask Question on How to write binary search algorithm?, Get Answer, Expert's Help, How to write binary search algorithm? Discussions

Write discussion on How to write binary search algorithm?
Your posts are moderated
Related Questions
How sparse matrix stored in the memory of a computer?

1. Define the following terms in a rule-based expert system? a) Knowledge base b) Inference engine 2. What is a fuzzy rule? Explain the difference between classical and fuzzy

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

What do we mean by algorithm? What are the characteristics of a good and relevant algorithm? An algorithm is "a step-by-step procedure for finishing some task'' An algorithm c

Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

Construct G for α, n, and W given as command line parameters. Throw away edges that have an asymmetric relation between nodes. That is, if A is connected to B, but B is not connect

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the


Assume you are in the insurance business. Find two examples of Type 2 slowly changing dimensions in that business. As an analyst on the project, write the specifications for applyi