Think about looking up a word in the dictionary. One way to do it would be to start at the a's and flip through the pages until you found the word you are looking for. This technique is called a linear search. The problem with linear search strategy is that if the word starts with an z, you will have to look through almost the entire dictionary before you found it. The way most people look for things in the dictionary is by guessing a place in the dictionary, then move forward or backward. This works because the words in the dictionary in in alphabetical order.
The binary search is a computer implementation of this technique. Lets say we are looking for a particular number in a sorted array of numbers. The computer looks in the middle of the array for the number it is looking for. If the number it finds is higher than the number it is looking for, it looks in the upper half of the array. If the number it finds is lower than the number it is looking for, it looks in the lower half of the array. It looks in the upper or lower half of the array by choosing the object in the middle of the half of the array and repeating the process it used for the entire array.
This algorithm is much faster than the one in which it looks at each item in order. If you look at each item in order, you might have to look at every item in the array before you find the one you are looking for. In binary search, you rule out half of the array at each step, so, if there are n items in the array, you will only have to look at log(n) of them in the worst case. Log(n) is the number which, if it is used at an exponent to 2 will give n. For example 3 is log(8); 10 is log(1025); 20 is log(1048576). You can see that for long array, binary search is much better than linear search.
C++ Binary Search:
/*
Compare X to the middle value (M) in L.
if X = M we are done.
if X < M we continue our search, but we can confine our search to the
first half of L and entirely ignore the second half of L.
if X > M we continue, but confine ourselves to the second half of L.
*/
#include ;
int bin_search(char arg, char arr[], int beg, int end) {
int mid = (beg + end) / 2;
if(arr[mid] < arg)
return bin_search(arg,arr,mid,end);
else if(arr[mid] > arg)
return bin_search(arg,arr,beg,mid);
else
return mid;
}
void main(void) {
char arr[26];
int i;
for(i=0;i<26;i++)
arr[i] = 'a' + i;
int loc = bin_search('a',arr,0,26);
fprint("Location found at %i",loc);
}
Here is the my COBOL implementation of the binary search from COBOL I.
********************************************************************
IDENTIFICATION DIVISION.
********************************************************************
PROGRAM-ID. BINARYSEARCH.
AUTHOR. SEAN BLANKENSHIP
DATE-WRITTEN. JUNE 12, 1998.
DATE-COMPILED. JUNE 12, 1998.
*******************************************************************
ENVIRONMENT DIVISION.
********************************************************************
CONFIGURATION SECTION.
SOURCE-COMPUTER. IBM.
OBJECT-COMPUTER. IBM.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
SELECT NUMBERS-FILE
ASSIGN TO DISK 'NUMBERS.IN'
ORGANIZATION IS LINE SEQUENTIAL.
SELECT SORT-NUMBERS-FILE
ASSIGN TO DISK 'NUMBERS.SR'.
SELECT REPORT-FILE
ASSIGN TO PRINTER 'CON'.
********************************************************************
DATA DIVISION.
********************************************************************
FILE SECTION.
*///////////////////////////////////////////////////////////////////
FD NUMBERS-FILE
LABEL RECORDS ARE STANDARD
RECORD CONTAINS 3 CHARACTERS
BLOCK CONTAINS 100 RECORDS
DATA RECORD IS NUMBERS-RECORD.
01 NUMBERS-RECORD.
05 NUMBERS-IN PIC 999.
SD SORT-NUMBERS-FILE
RECORD CONTAINS 3 CHARACTERS
DATA RECORD IS NUMBERS-SORT-RECORD.
01 NUMBERS-SORT-RECORD.
05 NUMBER-IN PIC 999.
FD REPORT-FILE
LABEL RECORDS ARE OMITTED
DATA RECORD IS REPORT-LINE.
01 REPORT-LINE PIC 999.
*///////////////////////////////////////////////////////////////////
WORKING-STORAGE SECTION.
*///////////////////////////////////////////////////////////////////
01 BINARY-STORAGE.
05 BINARY-HIGH PIC 999 VALUE 0.
05 BINARY-LOW PIC 999 VALUE 0.
05 BINARY-MIDDLE PIC 999 VALUE 0.
05 BINARY-FOUND PIC 9 VALUE 0.
05 BINARY-TARGET PIC 999 VALUE 0.
05 SEARCH-NUMBER PIC 999 VALUE 0.
05 BINARY-TOTAL-FLAG PIC 999 VALUE 0.
05 BINARY-JUMPS PIC 999 VALUE 0.
01 SEQUENTIAL-STORAGE.
05 SEQUENTIAL-TARGET PIC 999 VALUE 0.
05 SEQUENTIAL-FOUND PIC 9 VALUE 0.
05 SEQUENTIAL-JUMPS PIC 999 VALUE 0.
01 DISPLAY-STORAGE.
05 DIS-BINARY-TARGET PIC ZZ9.
05 DIS-BINARY-JUMPS PIC ZZ9.
05 DIS-SEQUENTIAL-TARGET PIC ZZ9.
05 DIS-SEQUENTIAL-JUMPS PIC ZZ9.
01 INPUT-RECORD-TABLE.
05 SINGLE-NUMBER OCCURS 100 TIMES PIC 999.
01 PRINT-RESULTS.
05 NUMBERS-OUT PIC ZZ9.
01 PROCESS-CHOICE PIC X.
01 EOF-FLAG-SRT PIC 9 VALUE 0.
01 EOF-FLAG-NUMBERS PIC 9 VALUE 0.
01 RANDOM-VAR PIC X.
********************************************************************
PROCEDURE DIVISION.
********************************************************************
0000-SORT-DATA.
SORT SORT-NUMBERS-FILE
ON ASCENDING KEY NUMBER-IN
USING NUMBERS-FILE
OUTPUT PROCEDURE 0001-MAIN-PROGRAM.
STOP RUN.
*///////////////////////////////////////////////////////////////////
0001-MAIN-PROGRAM.
PERFORM 0010-MAIN-MENU
UNTIL PROCESS-CHOICE = 'X' OR 'x'.
DISPLAY "MAIN MODULE SHUTDOWN" LINE 15 POSITION 30 ERASE.
*///////////////////////////////////////////////////////////////////
0010-MAIN-MENU.
DISPLAY " " ERASE.
DISPLAY "******************************" LINE 05 POSITION 28.
DISPLAY "* [B] BINARY SEARCH *" LINE 06 POSITION 28.
DISPLAY "* [S] SEQUENTIAL SEARCH *" LINE 07 POSITION 28.
DISPLAY "* [C] BINARY AND SEQUENTIAL *" LINE 08 POSITION 28.
DISPLAY "* [X] EXIT *" LINE 09 POSITION 28.
DISPLAY "******************************" LINE 10 POSITION 28.
ACCEPT PROCESS-CHOICE LINE 13 POSITION 40.
IF PROCESS-CHOICE = 'B' OR 'b'
PERFORM 1000-BINARY-MODULE
ELSE
IF PROCESS-CHOICE = 'S' OR 's'
PERFORM 1000-SEQUENTIAL-MODULE
ELSE
IF PROCESS-CHOICE = 'C' OR 'c'
PERFORM 1000-COMPARE-MODULE
END-IF
END-IF
END-IF.
*///////////////////////////////////////////////////////////////////
1000-BINARY-MODULE.
PERFORM 1005-INITIALIZE-SEARCH.
PERFORM 2000-BINARY-ARRAY
UNTIL EOF-FLAG-SRT = 1
DISPLAY " " ERASE.
DISPLAY "WHAT NUMBER TO SEARCH FOR?" LINE 2 POSITION 1.
ACCEPT BINARY-TARGET.
IF BINARY-TARGET NOT = 0
IF BINARY-TARGET IS < BINARY-TOTAL-FLAG
MOVE BINARY-TOTAL-FLAG TO BINARY-HIGH
PERFORM 2000-BINARY-SEARCH
UNTIL BINARY-FOUND = 1
MOVE BINARY-MIDDLE TO DIS-BINARY-TARGET
MOVE BINARY-JUMPS TO DIS-BINARY-JUMPS
DISPLAY " " ERASE
DISPLAY "BINARY SEARCH FOUND:"
DISPLAY DIS-BINARY-TARGET " IN "
DIS-BINARY-JUMPS " TRIES"
ELSE
DISPLAY " " ERASE
DISPLAY "THIS VALUE IS TOO LARGE"
END-IF
ACCEPT RANDOM-VAR
END-IF.
*///////////////////////////////////////////////////////////////////
1000-SEQUENTIAL-MODULE.
PERFORM 1005-INITIALIZE-SEARCH.
DISPLAY " " ERASE.
DISPLAY "WHAT NUMBER TO SEARCH FOR?" LINE 2 POSITION 1.
ACCEPT SEQUENTIAL-TARGET.
IF SEQUENTIAL-TARGET NOT = 0
OPEN INPUT NUMBERS-FILE
PERFORM 2000-SEQUENTIAL-SEARCH
UNTIL EOF-FLAG-NUMBERS = 1
MOVE SEQUENTIAL-TARGET TO DIS-SEQUENTIAL-TARGET
MOVE SEQUENTIAL-JUMPS TO DIS-SEQUENTIAL-JUMPS
DISPLAY " " ERASE
DISPLAY "SEQUENTIAL SEARCH FOUND:"
DISPLAY DIS-SEQUENTIAL-TARGET " IN "
DIS-SEQUENTIAL-JUMPS " TRIES"
ACCEPT RANDOM-VAR
CLOSE NUMBERS-FILE
END-IF.
*///////////////////////////////////////////////////////////////////
1000-COMPARE-MODULE.
PERFORM 1005-INITIALIZE-SEARCH.
PERFORM 2000-BINARY-ARRAY UNTIL EOF-FLAG-SRT = 1.
DISPLAY " " ERASE.
DISPLAY "WHAT NUMBER TO SEARCH FOR?" LINE 2 POSITION 1.
ACCEPT SEQUENTIAL-TARGET.
MOVE SEQUENTIAL-TARGET TO BINARY-TARGET.
IF SEQUENTIAL-TARGET NOT = 0
IF SEQUENTIAL-TARGET IS < BINARY-TOTAL-FLAG
MOVE BINARY-TOTAL-FLAG TO BINARY-HIGH
PERFORM 2000-BINARY-SEARCH
UNTIL BINARY-FOUND = 1
OPEN INPUT NUMBERS-FILE
PERFORM 2000-SEQUENTIAL-SEARCH
UNTIL EOF-FLAG-NUMBERS = 1
CLOSE NUMBERS-FILE
MOVE BINARY-MIDDLE TO DIS-BINARY-TARGET
MOVE BINARY-JUMPS TO DIS-BINARY-JUMPS
MOVE SEQUENTIAL-TARGET TO DIS-SEQUENTIAL-TARGET
MOVE SEQUENTIAL-JUMPS TO DIS-SEQUENTIAL-JUMPS
DISPLAY " " ERASE
DISPLAY "BINARY SEARCH FOUND:"
DISPLAY DIS-BINARY-TARGET " IN "
DIS-BINARY-JUMPS " TRIES"
DISPLAY " "
DISPLAY "SEQUENTIAL SEARCH FOUND:"
DISPLAY DIS-SEQUENTIAL-TARGET " IN "
DIS-SEQUENTIAL-JUMPS " TRIES"
ELSE
DISPLAY " " ERASE
DISPLAY "THIS VALUE IS TOO LARGE"
END-IF
ACCEPT RANDOM-VAR
END-IF.
*///////////////////////////////////////////////////////////////////
1005-INITIALIZE-SEARCH.
MOVE 0 TO EOF-FLAG-NUMBERS.
MOVE 0 TO SEQUENTIAL-JUMPS.
MOVE 0 TO BINARY-TARGET.
MOVE 0 TO BINARY-MIDDLE.
MOVE 0 TO BINARY-JUMPS.
MOVE 0 TO BINARY-LOW.
MOVE 0 TO BINARY-HIGH.
MOVE 0 TO BINARY-FOUND.
*///////////////////////////////////////////////////////////////////
2000-BINARY-ARRAY.
PERFORM 8000-READ-SRT.
ADD 1 TO BINARY-TOTAL-FLAG.
MOVE NUMBER-IN TO SINGLE-NUMBER (BINARY-TOTAL-FLAG).
* IF EOF-FLAG-SRT NOT = 1
* MOVE NUMBER-IN TO NUMBERS-OUT
* DISPLAY NUMBERS-OUT
* END-IF.
*///////////////////////////////////////////////////////////////////
2000-BINARY-SEARCH.
COMPUTE BINARY-MIDDLE = (BINARY-LOW + BINARY-HIGH) / 2.
IF BINARY-TARGET < SINGLE-NUMBER (BINARY-MIDDLE)
COMPUTE BINARY-HIGH = BINARY-MIDDLE
ADD 1 TO BINARY-JUMPS
ELSE
IF BINARY-TARGET > SINGLE-NUMBER (BINARY-MIDDLE)
COMPUTE BINARY-LOW = BINARY-MIDDLE
ADD 1 TO BINARY-JUMPS
ELSE
MOVE 1 TO BINARY-FOUND
END-IF
END-IF.
*///////////////////////////////////////////////////////////////////
2000-SEQUENTIAL-SEARCH.
PERFORM 8000-READ-NUMBERS.
ADD 1 TO SEQUENTIAL-JUMPS.
IF NUMBERS-IN IS = SEQUENTIAL-TARGET
MOVE 1 TO EOF-FLAG-NUMBERS.
*///////////////////////////////////////////////////////////////////
8000-READ-SRT.
RETURN SORT-NUMBERS-FILE INTO NUMBERS-SORT-RECORD
AT END MOVE 1 TO EOF-FLAG-SRT.
*///////////////////////////////////////////////////////////////////
8000-READ-NUMBERS.
READ NUMBERS-FILE INTO NUMBERS-RECORD
AT END
MOVE 1 TO EOF-FLAG-NUMBERS.