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 a B-Tree Justas AVL trees are balanced binary search trees, B-trees are balanced M-way search trees. A B-Tree of order M is either the empty tree or it is an M-way searc

Thread 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 either a stack

Which sorting algorithm is best if the list is already sorted? Why? Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order

Determine the importance of array Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.


what is far and near procedures in system programming?

difference between recursion and iteration

Describe different methods of developing algorithms with examples.

Postorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; }; postorder(struct NODE

CMY Model  The cyan, magenta, yellow (CMY) colour model is a subtractive model based on the colour absorption properties of paints and inks. As such it has become the standard