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
Implementation of queue using a singly linked list: While implementing a queue as a single liked list, a queue q consists of a list and two pointers, q.front and q.rear.


Write a C++ program with header and source les to store street addresses using the Doubly Linked List ADT. Modify the Node class from Lab Assignment 3 so that it becomes a node in

how to implement prims algorithm dynamically

What values are automatically assigned to those array elements which are not explicitly initialized? Garbage values are automatically assigned to those array elements that

The quick sort algorithm exploit design technique Divide and Conquer

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is called as

Following are some of the drawback of sequential file organisation: Updates are not simply accommodated. By definition, random access is impossible. All records should be

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