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
2. Write a note on i) devising ii) validating and iii) testing of algorithms.

Preconditions assertion A precondition is an assertion which should be true at the initiation of an operation. For instance, a square root operation can't accept a negative a

how to write prims algorithms? with example

explain collision resloving techniques in hasing

Q. Write down any four applications or implementation of the stack.                                     Ans. (i)       The Conversion of infix to postfix form (ii)

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


What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency

calculate gpa using an algorithm

The insertion procedure in a red-black tree is similar to a binary search tree i.e., the insertion proceeds in a similar manner but after insertion of nodes x into the tree T, we c