Binary search technique, Data Structure & Algorithms

Assignment Help:

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.

 


Related Discussions:- Binary search technique

Structural Induction, Let a be a well-formed formula. Let c be the number o...

Let a be a well-formed formula. Let c be the number of binary logical operators in a. (Recall that ?, ?, ?, and ? are the binary logical operators). Let s be the number of proposit

Explain the scan-line algorithm, Explain the Scan-Line Algorithm This i...

Explain the Scan-Line Algorithm This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of fillin

File organization, Define File organization''s and it''s types

Define File organization''s and it''s types

2 way merge sort, merge sort process for an example array {38, 27, 43, 3, 9...

merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the

Determine the warnock algorithm, Warnock's Algorithm A divide and conqu...

Warnock's Algorithm A divide and conquer algorithm Warnock (PolyList PL, ViewPort VP) If (PL simple in VP) then Draw PL in VP, else Split VP vertically and horiz

Example of single node with multiple elements, The class Element represents...

The class Element represents a single node that can be part of multiple elements on a hotplate and runs in its own thread. The constructor accepts the initial temperature and a hea

Entity relationship diagram, This question is based on the requirements of ...

This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

Chaining Method as Method of Collision Resolution , Q. The given values are...

Q. The given values are to be stored in a hash table 25, 42, 96, 101, 102, 162, 197 Explain how the values are hashed by using division technique of hashing with a table

Dynamic programming., Count Scorecards(30 points) In a tournament, N playe...

Count Scorecards(30 points) In a tournament, N players play against each other exactly once. Each game results in either of the player winning. There are no ties. You have given a

A full binary tree with 2n+1 nodes, A full binary tree with 2n+1 nodes have...

A full binary tree with 2n+1 nodes have n non-leaf nodes

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd