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

Calculation of storage complexity, Since memory is becoming more & cheaper,...

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog

Define prims algorithm, Define Prim's Algorithm Prim's  algorithm  is  ...

Define Prim's Algorithm Prim's  algorithm  is  a  greedy  algorithm  for  constructing  a  minimum  spanning  tree  of  a  weighted linked graph. It works by attaching to a bef

The complexity of multiplying two matrices, The complexity of multiplying t...

The complexity of multiplying two matrices of order m*n and n*p is    mnp

The quick sort algorithm exploit design technique, The quick sort algorithm...

The quick sort algorithm exploit design technique Divide and Conquer

Singly linked list , The two pointers per number of a doubly linked list pr...

The two pointers per number of a doubly linked list prepare programming quite easy. Singly linked lists as like the lean sisters of doubly linked lists. We need SItem to consider t

Calculates partial sum of an integer, Now, consider a function that calcula...

Now, consider a function that calculates partial sum of an integer n. int psum(int n) { int i, partial_sum; partial_sum = 0;                                           /* L

Multidimensional array, Q. The system allocates the memory for any of the m...

Q. The system allocates the memory for any of the multidimensional array from a big single dimensional array. Describe two mapping schemes that help us to store the two dimensi

Euclidean algorithm, The Euclidean algorithm is an algorithm to decide the ...

The Euclidean algorithm is an algorithm to decide the greatest common divisor of two positive integers. The greatest common divisor of N and M, in short GCD(M,N), is the largest in

Complexity of an algorithm, What do you mean by complexity of an algorithm?...

What do you mean by complexity of an algorithm? The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space need of the algorithm i

Programs, Develop a program that accepts the car registration( hint: LEA 43...

Develop a program that accepts the car registration( hint: LEA 43242010)

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