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

Sorting algorithm is best if the list is already sorted, Which sorting algo...

Which sorting algorithm is best if the list is already sorted? Why? Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order

Compound interest, Write the algorithm for compound interest

Write the algorithm for compound interest

What are the structures used in file-system implementation, What are the st...

What are the structures used in file-system implementation? Several on-disk and in-memory structures are used to execute a file system a. On-disk structure include P

B-tree, Unlike a binary-tree, each node of a B-tree may have a number of ke...

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

Graphs, floyd warshall algorithm

floyd warshall algorithm

Example of telephone directory, A telephone directory having n = 10 records...

A telephone directory having n = 10 records and Name field as key. Let us assume that the names are stored in array 'm' i.e. m(0) to m(9) and the search has to be made for name "X"

Array and two-dimensional array, Q. Describe the term array.  How do we rep...

Q. Describe the term array.  How do we represent two-dimensional arrays in memory?  Explain how we calculate the address of an element in a two dimensional array.

Explain the stack, QUESTION Explain the following data structures: ...

QUESTION Explain the following data structures: (a) List (b) Stack (c) Queues Note : your explanation should consist of the definition, operations and examples.

Unification algorithm, i want to write code for unification algorithm with ...

i want to write code for unification algorithm with for pattern matching between two expression with out representing an expression as alist

State in brief about assertion, State  in brief about assertion Asser...

State  in brief about assertion Assertion: A statement which should be true at a designated point in a program.

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