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
The operations of the Symbol ADT The operations of the Symbol ADT are the following. a==b-returns true if and only if symbols a and bare identical. a symbol bin Unico

HSV Colour Model Instead of a set of colour primaries, the HSV model uses colour descriptions that have a more intuitive appeal to a user. To give a colour specification, a use

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

Addition of new records in a Binary tree structure always occurs as leaf nodes, which are further away from the root node making their access slower. If this new record is to be ac

The structures of files vary from operating system to operating system. In this unit, we will discuss the fundamentals of file structures with the generic file organisations. A

what do we use asymptotic notation in study of algorithm?Describe various asymptotic notation and give their significance.

Ruby implementation of the Symbol ADT Ruby implementation of the Symbol ADT, as mentioned, hinges on making Symbol class instances immutable that corresponds to the relative la

Define tractable and intractable problems Problems that can be solved in polynomial time are known as tractable problems, problems that cannot be solved in polynomial time are

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

What do we mean by algorithm? What are the characteristics of a good and relevant algorithm? An algorithm is "a step-by-step procedure for finishing some task'' An algorithm c