Which one is faster A binary search of an ordered set of elements in an array or a sequential search of the elements?

Answer 1

There is no such thing as an insertion search. There is only insertion sort, which is a method of sorting an unsorted list. Sequential search (or linear search) is only used with unsorted lists. If the list is sorted, a logarithmic search is quicker, by starting from the middle. If the items is not here, it must be in the lower half or the upper half, thus one half of the list can be discarded. You then repeat by starting in the middle of the remaining half. Thus for a list of 15 items, you end up with a list of 7, then 3, then 1, then 0. Thus it takes 5 comparisons to determine that an item does not exist. With linear search it would take 15 comparisons to determine that an item does not exist. Thus logarithmic search is quicker, but only works with sorted lists.

Answer 2

Binary search is faster than sequential search on average.

Sequential search is only necessary with non-ordered arrays and has a worst-case time-complexity of O(n) for a set of n elements whereas searching an ordered array using binary search algorithm has a worst-case of O(log n).

In C Programming, we can implement binary search upon an ordered array of int as follows:

size_t binary_search (int* array, size_t size, int value) {

size_t lo, mid, hi; // variables to keep track of subarray bounds and middle index

if (array && size) { // ensure array arguments are valid

lo = 0;

hi = size; // note: half-open range [lo:hi)

while (hi>lo) {

mid = lo + ((hi - lo) / 2); // (re)calculate middle index of subarray [lo:hi)

if (array[mid]==value) {

return mid; // value found at array[mid]

}

// determine which half of the remaining subarray to search...

if (array[mid]<val) {

lo = mid+1; // search the upper half

} else {

hi = mid; // search the lower half

}

}

}

return size; // value not found or invalid array arguments

}

Answer 3

A binary search keeps splitting an array in half until the element is found or not found. With a binary search, you eliminate 1/2 the possible entries with each iteration. The number of operations for this logarithmic to the number of elements or in big O notation as O(log N) where N is the number of elements.

A sequential search at best finds the element on the first element and at worst the last nth element so on average the number of elements to be searched is N/2 or in big O notation simply O(N).