Binary search technique, Data Structure & Algorithms

Q. Describe the basic concept of binary search technique? Is it more efficient than the sequential search?        

Ans:

The binary search technique:-

This technique is applied to an ordered list where elements are arranged either in ascending order or descending order. The array is divided into two parts and the item being searched for is compared with item at the middle of the array. If they are equal the search is successful. Otherwise the search is performed in either the first half or second half of the array. If the middle element is greater than the item being searched for the search process is repeated in the first half of the array otherwise the process is repeated in the second half of the array. Each time a comparison is made, the number of element yet to be searched will be cut in half. Because of this division of array into two equal parts, the method is called a binary search.

In binary search, each iteration of the loop halves the size of the list to be searched. Thus the maximum number of key comparisons is approximately

2*log2n. This is quite an improvement over the sequential search, chiefly as the list gets larger. The binary search is, however, not guaranteed to be quicker for searching for small lists. Even though the binary search needs less number of comparisons, each comparison needs more computation or calculation. When n is small, the constant of proportionality can dominate. Therefore, in case of fewer number of elements in the list, a sequential search is enough.

 

Posted Date: 7/11/2012 1:35:23 AM | Location : United States







Related Discussions:- Binary search technique, Assignment Help, Ask Question on Binary search technique, Get Answer, Expert's Help, Binary search technique Discussions

Write discussion on Binary search technique
Your posts are moderated
Related Questions
Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

The following DNA sequences are extracted from promoter region of genes which are co-regulated by the same transcription factor (TF). The nucleotide segments capitalized in the giv

Hear is given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to give the output in three traversal orders. Write down an

Define about the class invariant A class invariant may not be true during execution of a public operation though it should be true between executions of public operations. For

For AVL trees the deletion algorithm is a little more complicated as there are various extra steps involved in the deletion of node. If the node is not a leaf node, then it contain

Q. What do you understand by the term sparse matrix? How sparse matrix is stored in the memory of a computer? Write down the function to find out the transpose of a sparse matrix u

A queue is a particular type of collection or abstract data type in which the entities in the collection are went in order and the principal functions on the collection are the add

Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

What is Assertions Introduction At every point in a program, there are generally constraints on the computational state that should hold for program to be correct. For ins