Binary search, Data Structure & Algorithms

In a sorted list, Binary search is carried out by dividing the list into two parts depends on the comparison of the key. Since the search interval halves each time, the iteration occur in the search. The search interval will look like as after each iteration

N, N/2,  N/4, N/8 , .......... 8, 4, 2, 1

The number of iterations (number of elements in the series) is not so evident through the above series. However, if we take logs of each element of the series, then

log2 N , log2 N -1,  log2 N-2, log2 N-3, .........., 3, 2, 1, 0

Since the sequence decrements through 1 each time the overall elements in the above series are log2 N + 1. Thus, the number of iterations is log2 N + 1 that is of the order of O(log2N).

Posted Date: 4/4/2013 6:19:34 AM | Location : United States







Related Discussions:- Binary search, Assignment Help, Ask Question on Binary search, Get Answer, Expert's Help, Binary search Discussions

Write discussion on Binary search
Your posts are moderated
Related Questions
Example of Area Subdivision Method The procedure will be explained with respect to an illustrative problem, with the image consisting of five objects, namely a triangle (T), qu

Q. Make a BST for the given sequence of numbers. 45,32,90,34,68,72,15,24,30,66,11,50,10 Traverse the BST formed in  Pre- order, Inorder and Postorder.

Implementing abstract data types A course in data structures and algorithms is hence a course in implementing abstract data types. It may seem that we are paying a lot of atten

Write an algorithm using pseudocode which takes temperatures input over a 100 day period (once per day) and output the number of days when the temperature was below 20C and the num

Thus far, we have seen the demonstration of a single queue, but several practical applications in computer science needs several queues. Multi queue is data structure in which mult

Explain th term input and output-  Pseudocode Input and output indicated by the use of terms input number, print total, output total, print "result is" x and so on.

how to implement multiple stack using single dimension array in c

State the range of operation of ADT Operations of the Range of T ADT includes following, where a, b ∈ T and r and s are values of Range of T: a...b-returns a range value (an

Explain the halting problem Given a computer program and an input to it, verify whether the program will halt on that input or continue working indefinitely on it.

What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n