Why would you write a program using array processing linear search and binary search of an array?

Answer 1

A linear search is effective when the order of elements in an array are not sorted by the value you are looking for. A binary search is effective when the order of elements is sorted by the value you are looking for.

Linear search sample data: 8 3 9 12 4 10 38 2 1 93 56 34

Binary search sample data: 1 2 3 4 8 9 10 12 34 38 56 93

In the first set of data, unsorted data cannot be searched using binary search. To find the value 38, a program must go through each element until it locates the 7th element; this is a total of 7 iterations. This method is effective when data is constantly being added and removed, and the overhead of a sorting algorithm would be less efficient than a binary search.

In the second set of data, the value 38 can be found by binary search. In the first iteration, a binary halfway point is found (we will choose element 6). Since 9 is less than 38, we know we need to go up. There are six remaining values, so we look at the 9th element (starting from the 6th element, there are six more, so we go half-way, 3 more, a total of 9). Here, we see the value is 34, still less than 38. There are three values remaining, so we go up 2 more. For the third iteration, the value is 56, which is more than our target of 38. Since we advanced 2 last time, we will decrease by 1 this time, and our fourth iteration will find the value 38.

As a matter of fact, in this data set, we will always find our answer in at most 4 iterations, while in the linear search, only the first 4 elements have a chance of being more efficient than the binary search. The problem then comes to down to if the sorting and binary search combined is faster than the linear search. For large data sets that are mostly static, binary searching is preferred. For rapidly changing data sets that would need constant sorting, a linear search may be preferred.

Note that if the data insertion algorithm maintains the sort order (by inserting each element at the correct index in memory), binary searching will likely be faster in the majority of cases. One can use a binary search for data insertion points, keeping the cost of data insertion minimized (but not as efficient as simply appending to the end) while maximizing search capabilities.