The Trick Of The Mind - Algorithms Binary Search |

Written by Mike James | |||||

Tuesday, 07 February 2023 | |||||

Page 4 of 4
## Divide And ConquerThe binary search algorithm is perhaps the most advanced of the simple algorithms. It is easy enough to understand both the problem and its overall solution – the details might be a little trickier, but still understandable. Algorithms of a similar type are often aimed at highly technical problems which tend to need a lot of preparation to understand, let alone solve or comprehend the solution. The general approach used by the binary search is referred to as divide and conquer. The idea is that if you can split a problem that involves N things into two problems involving N/2 things then there is a chance you can solve the problem more efficiently by repeating the process of splitting. Of course, there is no guarantee that this splitting will give you a better algorithm. However, if you can deal with a set of N/2 things faster than you can deal with N things and if putting the solutions back together to give you an overall solution doesn’t take too much extra work then the divide and conquer algorithm is preferable. In the case of the binary search, it is obvious that searching through N/2 things is faster than searching N things and putting the solution back together doesn’t take any extra time as in this case the solution to N/2 things is the solution to N things – if you have found it you have found it! Divide and conquer algorithms are usually described as “fast” or “quick” and the best known are the Fast Fourier Transform (FFT) and Quick Sort – both too involved to describe here, but the background to each is interesting. The story of the FFT is worth recounting. It was invented in 1965 by James Cooley and John Tukey and it is perhaps the most important algorithm of the 20 The QuickSort was invented by Tony Hoare in 1959 and published in 1961. Its practical effects weren’t as revolutionary as the FFT but they were still important. It too is a divide and conquer algorithm, but you can’t just divide a list into two parts and sort each part. The act of putting the two back together to form a single sorted list takes too many operations to be useful. The solution is to divide the list into two parts depending on a selected value – the pivot. The division is such that the portion to the left is less than the pivot and the portion to the right is bigger than the pivot. When the division reaches a single element the list is then sorted. It can be hard to understand QuickSort, but it is essentially the same as binary search where the target item is the pivot, which is used to create two portions of the list, one smaller and one larger. What is amazing is that repeating this gives you a sorted list and that it is faster than other methods. The value of the QuickSort algorithm is as much its status as a clever algorithm as its undeniable practical value. ## Not in this extract but in chapter:- Recursion
- Making A Hash
- Algorithms and Thought
## Summary-
Algorithms are what programs implement and to do this you have to make the specification of the algorithm precise enough to allow a non-intelligent agent to follow the instructions. -
Finding a book in a big library is a good problem to illustrate the idea of implementing an algorithm because it can be solved using simple and more advanced approaches. -
The simplest is linear search which works with a library of books in no particular order. -
You can also try picking books at random, but this isn’t a good algorithm. -
If the librarian has gone to the extra effort of putting the books into order, then you can use the binary search algorithm which is much more efficient. -
Specifying the binary search algorithm in detail is a very good example of how algorithms are converted into programs. -
The binary search algorithm is an example of a general class of divide and conquer algorithms, the most important of these being the Fast Fourier Transform and Quicksort. -
*Recursion is an alternative to iteration and it is particularly applicable to the binary search problem.* -
*The final algorithm for the book search problem is hashing. This is very efficient and doesn’t require the books to be sorted into order. If correctly implemented it can find a book in no more than a few attempts no matter how many books are involved.*
## The Trick Of The Mind - Programming & ComputationalThoughtBuy Now From Amazon Chapter List -
Little Languages Extract: Little Languages Arithmetic -
The Strange Incident of The Goto Considered Harmful Extract: The Goto Considered Harmful -
The Loop Zoo Extract The Loop Zoo Extract Advanced Loops -
Modules, Subroutines, Procedures and Functions Extract Modular Programming -
Algorithms Extract: Binary Search Extract: Recursion ***NEW!! -
The Object Of It All Extract Why Objects
<ASIN:1871962722> <ASIN:B09MDL5J1S> To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info |
|||||

Last Updated ( Tuesday, 07 February 2023 ) |