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

Inorder and preorder traversal to reconstruct a binary tree, Q. Using the f...

Q. Using the following given inorder and preorder traversal reconstruct a binary tree Inorder sequence is D, G, B, H, E, A, F, I, C

Write down a module to merge two linked lists, Two linked lists are having ...

Two linked lists are having information of the same type in ascending order. Write down a module to merge them to a single linked list that is sorted merge(struct node *p, stru

Graph, Multilist Representation of graph

Multilist Representation of graph

Explain how two dimensional arrays are represented in memory, Explain how t...

Explain how two dimensional arrays are represented in memory. Representation of two-dimensional arrays in memory:- Let grades be a 2-D array as grades [3][4]. The array will

ERM, Hi, can you give me a quote for an E-R diagram

Hi, can you give me a quote for an E-R diagram

frequenty count of function, Ask question find frequency count of function...

Ask question find frequency count of function- {for(i=1;i {for(j=1;j {for(k=1;k } } }

Convertion, how we can convert a graph into tree

how we can convert a graph into tree

Design and test a reference array, Instructions Design and test a r...

Instructions Design and test a reference array. Reference array stores the references to user supplied objects of different types. Just think it as a heterogeneous array wh

What is binary space partition, Binary Space Partition A binary space-p...

Binary Space Partition A binary space-partitioning (BSP) tree is an efficient method for determining object visibility by painting surfaces onto the screen from back to front,

Illustrate the operations of the symbol abstract data type, The operations ...

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

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