[SOLVED] Why is binary search slower than linear search for a list of 100 binary sorted numbers?

Question

So here I am finding the total number of 1's in list using binary search and linear search .For small input (100) ,why is that binary one is slower ,am i implementing it wrong way ?

https://code.sololearn.com/c2V2cJ3ZvKsa/?ref=app

Answer 1

From wikipedia: Binary search is faster than linear search except for small arrays.
https://en.m.wikipedia.org/wiki/Binary_search_algorithm

Answer 2

Robin thanks a lot for providing a detailed and a clear explanation of how it works and what I was doing wrong ,now i understand it much better

Answer 3

I read that it is slower for small arrays but why so? Aren't less operations performed for binary search!! like it divides the list into two half ,check condition and loop continues
and if a element is at 50th position, loop will run 5-6 times
while in linear one it just checks condition and loop continues and if a element is at 50th position ,Loop will run 49 times

Answer 4

Binary search is faster than linear search without any doubt, with a O(log n) runtime complexity. On the other hand linear search has complexity of O(n) - or linear time complexity

Note those big O notations specifies the worst the algorithm can go for, so if you linear searched 1 in this list [1, 2, 3] it will be faster than other method for sure.

But again those Big O notations specifies the worst it can do, which may be the answer you looking for

Answer 5

Thks Martin Taylor ,but I don't get it how is linear search fast ,like for a list of 100 ,if first 50 are zeroes ,then Loop will run 50 times but in binary search the loop will run only 6 times,shudn't it be faster if I am not thinking wrong ,but there are other operations as well being performed in binary search like checking for if conditions ,dividing array into two two subarrays,and finding mid element ,so all that slows down binary search?

Also if you run this binary search for list with numbers like 1000 and above it performs better than linear search

Answer 6

I guess you need to understand Big O notation. But I am not completely sure.

Answer 7

Robin how are you able to type long answers? I am not able to type half of that. Sololearn gives a character limit for my device

Answer 8

Robin Ah. I see