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
Question 1 Write a program in 'C' to read N numbers and print them in descending order Question 2 Discuss the properties of ADT Question 3 Write a note on

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

One of the main problems with the linear queue is the lack of appropriate utilization of space. Assume that the queue can store 100 elements & the complete queue is full. Thus, it

Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer? O (1)


Demonstrate that Dijkstra's algorithm does not necessarily work if some of the costs are negative by finding a digraph with negative costs (but no negative cost dicircuits) for whi

algorithm for multiplication of two sparse matrices using link list

State about the pre- and post conditions Programmers can easily document other pre- and post conditions and class invariants, though, and insert code to check most value preco

Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

Explain an efficient way of storing a sparse matrix in memory.   A matrix in which number of zero entries are much higher than the number of non zero entries is called sparse mat