[algorithm] What is the difference between Linear search and Binary search?

What is the difference between Linear search and Binary search?

A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search - the time taken to search the list gets bigger at the same rate as the list does.

A binary search is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you're looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc. This is pretty much how humans typically look up a word in a dictionary (although we use better heuristics, obviously - if you're looking for "cat" you don't start off at "M"). In complexity terms this is an O(log n) search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation.

For a clear understanding, please take a look at my codepen implementations https://codepen.io/serdarsenay/pen/XELWqN

Biggest difference is the need to sort your sample before applying binary search, therefore for most "normal sized" (meaning to be argued) samples will be quicker to search with a linear search algorithm.

Here is the javascript code, for html and css and full running example please refer to above codepen link.

var unsortedhaystack = [];
var haystack = [];
function init() {
  unsortedhaystack = document.getElementById("haystack").value.split(' ');
}
function sortHaystack() {
  var t = timer('sort benchmark');
  haystack = unsortedhaystack.sort();
  t.stop();
}

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

function lineerSearch() {
  init();
  var t = timer('lineerSearch benchmark');
  var input = this.event.target.value;
  for(var i = 0;i<unsortedhaystack.length - 1;i++) {
    if (unsortedhaystack[i] === input) {
      document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return unsortedhaystack[i]; 
    }
  }
}

function binarySearch () {
  init();
  sortHaystack();
  var t = timer('binarySearch benchmark');
  var firstIndex = 0;
  var lastIndex = haystack.length-1;
  var input = this.event.target.value;

  //currently point in the half of the array
  var currentIndex = (haystack.length-1)/2 | 0;
  var iterations = 0;

  while (firstIndex <= lastIndex) {
    currentIndex = (firstIndex + lastIndex)/2 | 0;
    iterations++;
    if (haystack[currentIndex]  < input) {
      firstIndex = currentIndex + 1;
      //console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
    } else if (haystack[currentIndex] > input) {
      lastIndex = currentIndex - 1;
      //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
    } else {
      document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return true;
    }
  }
}

Think of it as two different ways of finding your way in a phonebook. A linear search is starting at the beginning, reading every name until you find what you're looking for. A binary search, on the other hand, is when you open the book (usually in the middle), look at the name on top of the page, and decide if the name you're looking for is bigger or smaller than the one you're looking for. If the name you're looking for is bigger, then you continue searching the upper part of the book in this very fashion.

binary search runs in O(logn) time whereas linear search runs in O(n) times thus binary search has better performance

Linear Search looks through items until it finds the searched value.

Efficiency: O(n)

Example Python Code:

test_list = [1, 3, 9, 11, 15, 19, 29]
test_val1 = 25
test_val2 = 15

def linear_search(input_array, search_value):
    index = 0
    while (index < len(input_array)) and (input_array[index] < search_value):
        index += 1
    if index >= len(input_array) or input_array[index] != search_value:
        return -1

    return index


print linear_search(test_list, test_val1)
print linear_search(test_list, test_val2)

Binary Search finds the middle element of the array. Checks that middle value is greater or lower than the search value. If it is smaller, it gets the left side of the array and finds the middle element of that part. If it is greater, gets the right part of the array. It loops the operation until it finds the searched value. Or if there is no value in the array finishes the search.

Efficiency: O(logn)

Example Python Code:

test_list = [1, 3, 9, 11, 15, 19, 29]
test_val1 = 25
test_val2 = 15

def binary_search(input_array, value):
    low = 0
    high = len(input_array) - 1
    while low <= high:
        mid = (low + high) / 2
        if input_array[mid] == value:
            return mid
        elif input_array[mid] < value:
            low = mid + 1
        else:
            high = mid - 1

    return -1


print binary_search(test_list, test_val1)
print binary_search(test_list, test_val2)

Also you can see visualized information about Linear and Binary Search here: https://www.cs.usfca.edu/~galles/visualization/Search.html

A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search - the time taken to search the list gets bigger at the same rate as the list does.

A binary search is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you're looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc. This is pretty much how humans typically look up a word in a dictionary (although we use better heuristics, obviously - if you're looking for "cat" you don't start off at "M"). In complexity terms this is an O(log n) search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation.

As an example, suppose you were looking for U in an A-Z list of letters (index 0-25; we're looking for the value at index 20).

A linear search would ask:

list[0] == 'U'? No.
list[1] == 'U'? No.
list[2] == 'U'? No.
list[3] == 'U'? No.
list[4] == 'U'? No.
list[5] == 'U'? No.
... list[20] == 'U'? Yes. Finished.

The binary search would ask:

Compare list[12] ('M') with 'U': Smaller, look further on. (Range=13-25)
Compare list[19] ('T') with 'U': Smaller, look further on. (Range=20-25)
Compare list[22] ('W') with 'U': Bigger, look earlier. (Range=20-21)
Compare list[20] ('U') with 'U': Found it! Finished.

Comparing the two:

• Binary search requires the input data to be sorted; linear search doesn't
• Binary search requires an ordering comparison; linear search only requires equality comparisons
• Binary search has complexity O(log n); linear search has complexity O(n) as discussed earlier
• Binary search requires random access to the data; linear search only requires sequential access (this can be very important - it means a linear search can stream data of arbitrary size)

Linear search also referred to as sequential search looks at each element in sequence from the start to see if the desired element is present in the data structure. When the amount of data is small, this search is fast.Its easy but work needed is in proportion to the amount of data to be searched.Doubling the number of elements will double the time to search if the desired element is not present.

Binary search is efficient for larger array. In this we check the middle element.If the value is bigger that what we are looking for, then look in the first half;otherwise,look in the second half. Repeat this until the desired item is found. The table must be sorted for binary search. It eliminates half the data at each iteration.Its logarithmic.

If we have 1000 elements to search, binary search takes about 10 steps, linear search 1000 steps.

Try this: Pick a random name "Lastname, Firstname" and look it up in your phonebook.

1st time: start at the beginning of the book, reading names until you find it, or else find the place where it would have occurred alphabetically and note that it isn't there.

2nd time: Open the book at the half way point and look at the page. Ask yourself, should this person be to the left or to the right. Whichever one it is, take that 1/2 and find the middle of it. Repeat this procedure until you find the page where the entry should be and then either apply the same process to columns, or just search linearly along the names on the page as before.

Time both methods and report back!

[also consider what approach is better if all you have is a list of names, not sorted...]

A linear search works by looking at each element in a list of data until it either finds the target or reaches the end. This results in O(n) performance on a given list. A binary search comes with the prerequisite that the data must be sorted. We can leverage this information to decrease the number of items we need to look at to find our target. We know that if we look at a random item in the data (let's say the middle item) and that item is greater than our target, then all items to the right of that item will also be greater than our target. This means that we only need to look at the left part of the data. Basically, each time we search for the target and miss, we can eliminate half of the remaining items. This gives us a nice O(log n) time complexity.

Just remember that sorting data, even with the most efficient algorithm, will always be slower than a linear search (the fastest sorting algorithms are O(n * log n)). So you should never sort data just to perform a single binary search later on. But if you will be performing many searches (say at least O(log n) searches), it may be worthwhile to sort the data so that you can perform binary searches. You might also consider other data structures such as a hash table in such situations.

Make sure to deliberate about whether the win of the quicker binary search is worth the cost of keeping the list sorted (to be able to use the binary search). I.e. if you have lots of insert/remove operations and only an occasional search the binary search could in total be slower than the linear search.

A linear search starts at the beginning of a list of values, and checks 1 by 1 in order for the result you are looking for.

A binary search starts in the middle of a sorted array, and determines which side (if any) the value you are looking for is on. That "half" of the array is then searched again in the same fashion, dividing the results in half by two each time.