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
Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X

Method to measure address of any element of a matrix stored in memory. Let us consider 2 dimensional array a of size m*n further consider that the lower bound for the row index

In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order

Q. Reverse the order of the elements on a stack S    (i) by using two additional stacks (ii) by using one additional queue. Ans :      L e t S be the stac

Q. Construct a complete binary tree with depth 3 for this tree which is maintained in the memory using the linked representation. Make the adjacency list and adjacency matrix for t

Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of

Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

Explain Internal and External Nodes  To  draw  the  tree's  extension  by  changing  the  empty  subtrees  by  special nodes. The  extra  nodes shown by little squares are know

Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn