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
Here is a diagram showing similarities between documents; this is an actual set of physics lab assignments from a large university. Each node (square) in the graph is a doc

Write an algorithm for binary search. What are its limitations? .

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Q. Write an algorithm that counts number of nodes in a linked list.                                       A n s . Algo rithm to Count No. of Nodes in Linked List C

Q.1 What is an algorithm? What are the characteristics of a good algorithm? Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space c

Program Insertion of a node into any Circular Linked List Figure depicts a Circular linked list from which an element was deleted. ALGORITHM (Deletion of an element from a

Explain th term input and output-  Pseudocode Input and output indicated by the use of terms input number, print total, output total, print "result is" x and so on.

What is quick sort? Quick sort is a sorting algorithm that uses the idea if split and conquer. This algorithm chooses an element called as pivot element; search its position in

Use a random number generator to create 10 numbers between 1 and 1000 and store them in 2 different arrays.  The first array should contain the numbers as they are generated.  The