Binary Chop Algorithm
Site Map Feedback
Download: FileChopper.h		Binary Chop Checksums Time QuickSearch Word Finder
	The Binary Chop Search Algorithm

Binary chop is how a you would use a Telephone Directory in a foreign country; when you don't have any experience of the foreign surnames to know the likely distribution.
So the best way to find a name is to open (near) the middle page of the Directory and see what name is at the head of the page.
You can now focus your attention on finding the name in one half of the Directory because the names are in order and you can see if the name you are looking for comes before or after the name in the middle.
In one step you can ignore half the Directory and repeat the process to see which of the two remaining quarters the name will be in.
Binary chop halves the amount of data you need to search with each look.
It only works for sorted arrays but makes the search as fast as a balanced binary tree.
Binary Chop is also used in the FixedArray structure.
Here's the basic algorithm:

  int stt=0; // Start
  int mid=0;
  int end=NumberOfListItems;
  while(stt!=end) {
    mid=(stt+end)/2;
    if(List[mid]==target) break;   // Found it!
    if(List[mid]> target) end=mid; // It may be in the first half...
    else stt=mid+1;                // It may be in the last half...
  }
  bool Found=(List[mid]==target);

Imagine you have a ListBox containing alphabetically sorted words a user has added to their Custom Dictionary.
To see if a word is in that ListBox you could use the ListBox.Find method, but those are usually going to search every entry in order.
The following code will search the List much faster (as if it were a Tree) and return the index of the text if it was found, or -1 if it wasn't found:

int CDictionary::FindCustom(const CString& Target) {
  CListBox* Custom=(CListBox*)GetDlgItem(IDC_Custom);
  int stt=0; // Start
  int mid; // Middle will be calculated later.
  int end=Custom->GetCount();
  CString S;
  int i=-1; // The result of comparisons, zero if equal.
  while(stt!=end) {
    mid=(stt+end)/2;
    Custom->GetText(mid,S);
    i=S.CompareNoCase(Target);
    if(i==0) break;
    if(i>0) end=mid;
    else stt=mid+1;
  }
  return i ? -1 : mid;
}

• FileChopper.h

FileChopper.h uses Binary Chop Search to find a text record in a file using the first field as a Key.
The CFileChopper class uses the Array.h and CSV.h files.
Create a text file with the following eight lines of text:

"FIFTH", FIVE
"FIRST" , ONE
FOURTH, FOUR
NINTH, NINE
SECOND, TWO
SEVENTH, SEVEN
SIXTH, SIX
TENTH, TEN
THIRD, THREE

The following code will read the file, searching for the line starting with "FIRST",
then print the next Field in the debug window:

CString S;
CFileChopper Chop(&S, "t.txt",20);
TRACE("\r\n");
if(Chop.Find("FIRST"  )) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("SECOND" )) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("THIRD"  )) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("FOURTH" )) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("FIFTH"  )) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("SIXTH"  )) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("SEVENTH")) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("EIGHTH" )) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("NINTH"  )) {Chop.GetNextField(); TRACE(S+", ");}
if(Chop.Find("TENTH"  )) {Chop.GetNextField(); TRACE(S+"\r\n");}
TRACE("\r\n");

This is the output in the debug window:

ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN

Of course, there is little point Binary Chopping a File this small.
If you search the Internet for Ispell Dictionaries you should be able to find English or other Dictionaries to download with tens of thousands of alphabetically sorted words, one on each line of the Text File.
These Files are perfect for showing how fast this algorithm can be.
16 File Seeks will find a word in a 65536 word Dictionary File.
A Dictionary File with half a million words takes only 19 File Seeks.
The bigger the File, the better!

---

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

---