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
7. String manipulation 7.a Write a C Program using following string manipulation functions a) strcpy b) strncpy c) strcmp d) strncmp e) strlen f) strcat

c++ To calculate the amount to be paid by a customer buying yummy cupcakes for his birth day party

Q. Write down an algorithm to merge the two sorted arrays into the third array. Do  not perform the sort function in the third array.                           Ans: void m

a. Determine the result of inserting the keys 4,19, 17, 11, 3, 12, 8, 20, 22, 23, 13, 18, 14, 16, 1, 2, 24, 25, 26, 5 in order to an empty B-Tree of degree 3. Only draw the configu

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

Step 1: Choose a vertex in the graph and make it the source vertex & mark it visited. Step 2: Determine a vertex which is adjacent to the source vertex and begun a new search if

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

Any Binary search tree has to contain following properties to be called as a red- black tree. 1. Each node of a tree must be either red or black. 2. The root node is always b