Comparisons between linear and binary search, Data Structure & Algorithms

Assignment Help:

Comparative Study of Linear and Binary Search

Binary search is lots quicker than linear search. Some comparisons are following:

NUMBER OF ARRAY ELEMENTS EXAMINED

array size   |     linear search    binary search

                  |        (avg. case)    (worst case)

--------------------------------------------------------

8                    |        4                  4

128                |       64                  8

256                |      128                9

1000              |      500               11

100,000           |    50,000            18

A binary search on an array is O(log2 n) because at each test, you can "throw out" one half of the search space or array while a linear search in an array is O(n).

It is noteworthy that, for extremely small arrays a linear search can prove quicker than a binary search. Though, as the size of the array to be searched increases, the binary search is the clear winner in terms of many comparisons and therefore total speed.

Still, the binary search has some disadvantage. First, it needs that the data to be searched be in sorted order. If there is just one element out of order within the data being searched, it can throw off the entire process. While presented with a set of unsorted data, the efficient programmer has to decide whether to sort the data & apply a binary search or simply apply the less-efficient linear search. Is the cost of sorting the data is worth the raise in search speed gained along with the binary search? If you are searching only once, then it is possibly to better do a linear search in most cases.


Related Discussions:- Comparisons between linear and binary search

Define approximating smooth surfaces with polygon nets, Approximating smoot...

Approximating smooth surfaces with Polygon nets Networks of polygons are used to represent smooth surfaces. They are, of course, only an approximation to the true surface, but

Binary tree and binarytree parts, Q. What do you understand by the term Bin...

Q. What do you understand by the term Binary Tree? What is the maximum number of nodes which are possible in a Binary Tree of depth d. Explain the terms given below with respect to

Relative and direct files, Each data record contains a fixed place in a rel...

Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

Various passes of bubble sort, Q. Show the various passes of bubble sort on...

Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6           Ans: The given data is as follows:- Pass 1:-     11   15   2     13

Boar corloring, Board coloring , C/C++ Programming

Board coloring , C/C++ Programming

Degree of node, Q. The degree of a node is defined as the number of childre...

Q. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

Program, insertion and deletion in a tree

insertion and deletion in a tree

Applications of the queue, Write down any four applications of the queues. ...

Write down any four applications of the queues.                                                            Ans. A pp li cation of Queue is given below (i)  Queue is

Calculate address of an element in an array., Q. Explain the technique to c...

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

Explain merge sort, Question 1 Explain the use of algorithms in computing ...

Question 1 Explain the use of algorithms in computing Question 2 Explain time complexity and space complexity of an algorithm Question 3 Explain how you can analyz

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