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
Binary Search Tree let three types of traversals by its nodes. They are: Pre Order Traversal In Order Traversal Post Order Traversal In Pre Order Traversal, we ca

Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Explain an efficient and effective way of storing two symmetric matrices of the same order in the memory. A n-square matrix array will be symmetric if a[j][k]=a[k][j] for all j

Q. Explain the technique to calculate the address of an element in an array. A  25 × 4  matrix array DATA is stored in memory in 'row-major order'. If base  address is 200 and

Run time complexity of an algorithm is depend on

The smallest element of an array's index is called its Lower bound.

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

Row Major Representation In memory the primary method of representing two-dimensional array is the row major representation. Under this representation, the primary row of the a

what are registers? why we need register? Definition? Types? What registers can do for us?

An advertising project manager developed the network diagram shown below for a new advertising campagign.  In addition, the manager gathered the time information for each activity,