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
Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of

What is Access Restrictions Structured containers with access restrictions only allow clients to add, remove and examine elements at certain locations in their structure. For

How many nodes in a tree have no ancestors 1 node in atree have no ancestors.

A driver takes shortest possible route to attain destination. The problem which we will discuss here is similar to this type of finding shortest route in any specific graph. The gr

Example of Back Face Detection Method To illustrate the method, we shall start with the tetrahedron (pyramid) PQRS of     Figure with vertices P (1, 1, 2), Q (3, 2, 3), R (1,

Threaded Binary Tree:- By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using


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

The below formula is used to calculate n: n = (x * x)/ (1 - x). Value x = 0 is used to stop the algorithm. Calculation is repeated using values of x until value x = 0 is input. The

What is an unreachable code assertion An unreachable code assertion can be placed at the default case; if it's every executed, then program is in an erroneous state. A loop in