Linear Search, Binary Search and other Searching Linear search program in c By Prelude Searching for data is one of the fundamental fields of computing. Often, the difference between a fast program and a slow one is the use of a good algorithm for the data set. This article will focus on searching for data stored in a linear data structure such as an array or linked list. Naturally, the use of a or will result in more efficient searching, but more often than not an or will be used. It is necessary to understand good ways of searching data structures not designed to support efficient search. The idiom should be familiar to most readers. For those that are not familiar with it, that is how it is done. The basic sequential search algorithm can be improved in a number of ways. One of those ways is to assume that the item being searched for will always be in the list. This way you can avoid the two termination conditions in the loop in favor of only one. Of course, that creates the problem of a failed search. If we assume that the item will always be found, how can we test for failure. The answer is to use a list that is larger in size than the number of items by one. A list with ten items would be allocated a size of eleven for use by the algorithm. The concept is much like C-style strings and the nul terminator. The nul character has no practical use except as a dummy item delimiting the end of the string. The speed improvement is for failed searches. Because the absence of an item can be determined more quickly, the average speed of a failed search is twice that of previous algorithms on average. By combining the Quick sequential search and the Ordered sequential search, one can have a highly tuned sequential search algorithm. Exercise 1: The last paragraph suggests an efficient sequential search algorithm. Use what you've learned to implement it. Exercise 2: Write a test program to verify the correct operation of the functions given. Exercise 3: Can you think of a more efficient way to perform sequential search. What about a non-sequential search. Self Organizing Search For lists that do not have a set order requirement, a self organizing algorithm may be more efficient if some items in the linear search program in c are searched for more frequently than others. By bubbling a found item toward the front of the list, future searches for that item will be executed more quickly. This speed improvement takes advantage of the fact that 80% of all operations are performed on 20% of the items in a data set. If those items are nearer to the front of the list then search will be sped up considerably. The first solution that comes to mind is to move the found item to the front. A solution that is just as effective, but takes longer to reach the optimal limit is to swap the found item with the previous item in the list. This algorithm is where arrays excel over linked lists for our data set of integers. The cost of swapping two integers is less than that of surgery with pointers. If so, at what point does the performance increase make the cost of restructuring the list practical. Exercise 5: Tune source 6 to run as quickly as possible. Would it make sense to use in production code. Exercise 6: Rewrite source 8 to use linked linear search program in c. Compare and contrast the two functions. Is such a change worth the effort. Is it an improvement in any way. Binary Search All of the sequential search algorithms have the same problem; they walk over the entire list. Some of our improvements work to minimize the cost of traversing the whole data set, but those improvements only cover up what is really a problem with the algorithm. By thinking of the data in a different way, we can make speed improvements that are much better than anything linear search program in c search can guarantee. Consider a list in ascending sorted order. It would work to search from the beginning until an item is found or the end is reached, but it makes more sense to remove as much of the working data set as possible so that the item is found more quickly. If we started at the middle of the list we could determine which half the item is in because the list is sorted. This effectively divides the working range in half with a single test. By repeating the procedure, the result is a highly efficient search algorithm called binary search. The actual algorithm is surprisingly tricky to implement considering the apparent simplicity of the concept. Readers are expected to trace its execution on paper and with a test program to fully understand its elegance. Binary search is very efficient, but it can be improved by writing a variation that searches more like humans do. Consider how you would search for a name in the phonebook. I know of nobody who would start in the middle if they are searching for a name that begins with B. They would begin at the most likely location and then use that location as a gauge for the next most likely location. Such a search is called interpolation search because it estimates the position of the item being searched for based on the upper and lower bounds of the range. If you made it this far you should be writing test code and doing paper runs of any new algorithm you meet as habit. If not, now you have no choice because I am not going to say just how this function works. With an average time complexity of O log log ninterpolation search beats binary search's O log n easily. However, tests have shown that interpolation search isn't significantly better in practice unless the data set is very large. Otherwise, binary search is faster. Exercise 8: Explain why binary search is so tricky to implement. Show an example of an incorrect implementation. Exercise 9: Binary search uses a divide-and-conquer algorithm. What other problems can this algorithm solve. Exercise 10: Determine the lower limit where interpolation search linear search program in c substantially better than binary search. Exercise 11: Write a search function that uses interpolation search until the lower limit is reached, then switches to binary search. Is the extra performance worth the effort. Conclusion Searching is an important function in computer science. Many advanced algorithms and data structures have been devised for the sole purpose of making searches more efficient. And as the data sets become larger and larger, good search algorithms will become more important. At one point in the history of computing, sequential search was sufficient. But that quickly changed as the value of computers became apparent. Linear search has many interesting properties in its own right, but is also a basis for all other search algorithms. Learning how it works is critical. Binary search is the next logical step in searching. By dividing the working data set in half with each comparison, logarithmic performance, O log nis achieved. That performance can be improved significantly when the data set is very large by using interpolation search, and improved yet again by using binary search when the data set gets smaller.
