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 the gpa of six students

Binary tree creation struct NODE { struct NODE *left; int value; struct NODE *right; }; create_tree( struct NODE *curr, struct NODE *new ) { if(new->val

Binary search technique:-  This technique is applied to an ordered list where elements are arranged either in ascending order or descending order. The array is separated into t

In the array implementation of the lists, we will use the array to hold the entries and a separate counter to keep track of the number of positions are occupied. A structure will b

Implementation of Stack :- Stacks can be executed in the 2 ways: a)  Arrays b)  Linked List

A Sort which relatively passes by a list to exchange the first element with any element less than it and then repeats with a new first element is called as      Quick sort.

include include include /* Definition of structure node */ typedef struct node { int data; struct node *next; } ; /* Definition of push function */

algorithm and flow chart to find weather the given numbers are positive or negative or neutral

In this sorting algorithm, multiple swapping occurs in one pass. Smaller elements move or 'bubble' up to the top of the list, so the name given to the algorithm. In this method,

Question 1 Explain how the shuttle sort algorithm works by making use of the following list of integers:11, 4, 2, 8, 5, 33, 7, 3, 1, 6. Show all the steps. Question 2