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?

#input restricted DEQUE, #why all the 4 operations i.e. insertion n del...

#why all the 4 operations i.e. insertion n deletion from rear end and front end is valid in input restricted DEQUE

Programs, Develop a program that accepts the car registration( hint: LEA 43...

Develop a program that accepts the car registration( hint: LEA 43242010)

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

The complexity of multiplying two matrices, The complexity of multiplying t...

The complexity of multiplying two matrices of order m*n and n*p is    mnp

Basic concept of the primitive data structures, Q. Explain the basic concep...

Q. Explain the basic concept of the primitive data structures.                                             Ans. The concept of P r i m i t i ve Data

How do collisions happen during hashing, How do collisions happen during ha...

How do collisions happen during hashing? Usually the key space is much larger than the address space, thus, many keys are mapped to the same address. Assume that two keys K1 an

Multiqueue, data structure for multiqueue

data structure for multiqueue

Explain linked list, Linked List  A linked list is a linear collection...

Linked List  A linked list is a linear collection of data elements called nodes. The linear order is given by pointer. Every node is divided into 2 or more parts.

Graph, Multilist Representation of graph

Multilist Representation of graph

Algorithm for a function that takes in integer as argument, Write a detaile...

Write a detailed description of a function that takes in an integer as an argument, then prints out the squares of all positive integers whose squares are less than the input. (The

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