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

Assignment Help:

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.


Related Discussions:- How to write binary search algorithm?

Explain the sum of subset problem, a. Explain the sum of subset problem. Ap...

a. Explain the sum of subset problem. Apply backtracking to solve the following instance of sum of subset problem: w= (3, 4, 5, 6} and d = 13. Briefly define the method using a sta

Size of stack, The size of stack was declared as ten. Thus, stack cannot ho...

The size of stack was declared as ten. Thus, stack cannot hold more than ten elements. The major operations which can be performed onto a stack are push and pop. However, in a prog

Explain the concept of colouring, Colouring The use of colours in CAD/C...

Colouring The use of colours in CAD/CAM has two main objectives : facilitate creating geometry and display images. Colours can be used in geometric construction. In this case,

Dqueue, algorithm of output restricted queue.

algorithm of output restricted queue.

Sparse metrics, Q. Define the sparse metrics and also explain the represent...

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

Insertion sort, Data array A has data series from 1,000,000 to 1 with step ...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Stacks, Q. Explain w hat are the stacks? How can we use the stacks  to chec...

Q. Explain w hat are the stacks? How can we use the stacks  to check whether an expression is correctly parentheses or not. For example (()) is well formed but (() or )()( is not w

Applications of binary trees, In computer programming, Trees are utilized ...

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Gam

Abstract Data Types, A useful tool which is used for specifying the logical...

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

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd