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
Explain an efficient and effective way of storing two symmetric matrices of the same order in the memory. A n-square matrix array will be symmetric if a[j][k]=a[k][j] for all j

advanatges of dynamic data structure in programming

What are the properties of an algorithsm?

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Do you have a library solution for this problem?

Illustrate the Back Face Detection Method A single polyhedron is a convex solid, which has no external angle between faces less  than 180° and there is a simple object space me

Merge sort is a sorting algorithm which uses the basic idea of divide and conquers. This algorithm initially divides the array into two halves, sorts them separately and then merge

what do we use asymptotic notation in study of algorithm?Describe various asymptotic notation and give their significance.

Q. Implement a stack making use of the linked list. Show the PUSH and POP operations both. A n s . Stack implemantation using linked list # include # include

A useful tool which is used for specifying the logical properties of a data type is called the abstract data type or ADT. The term "abstract data type" refers to the fundamental ma