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
(1) Sort a list of distinct numbers in ascending order, using the following divide- and-conquer strategy (Quicksort): divide the list of numbers into two lists: one that contains a

Determine about the Post conditions assertion A  post condition is an assertion which should be true at completion of an operation. For instance, a post condition of the squ

A binary tree of depth "d" is an almost complete binary tree if  A) Every leaf in the tree is either at level "d" or at level "d-1"  B)  For any node "n" in the tree with a

You are supposed to do the following: Write a parallel implementation of the raytracer using pthreads. Measure and compare the execution times for (i) the sequential ver

Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff

How can a lock object be called in the transaction? By calling Enqueue and Dequeue in the transaction.

Determination of Time Complexity The RAM Model The random access model (RAM) of computation was devised through John von Neumann to study algorithms. In computer science,

what happen''s in my computer when i input any passage

Q. Describe the adjacency matrix and make the same for the given undirected graph.    Ans: The representation of Adjacency Matrix: This representation consists of

A binary search tree (BST), which may sometimes also be named a sorted or ordered binary tree, is an edge based binary tree data structure which has the following functionalities: