What is Binary Search Algorithm?

Binary Search Algorithm

Algorithm: (Binary Search) BINARY (DATA, LB, UB, ITEM, LOC)

 Here DATA is a sorted array with lower bound LB and upper bound UB, and ITEM is a given item of information. The variables BEG, END and MID denote, respectively, the beginning, end and middle locations of a segment of elements of DATA. This algorithm finds the location LOC of ITEM in DATA or sets LOC = NULL.

1.      [Initialize segment variables.]

Set BEG := LB, END := UB and MID = INT((BEG + END)/2).

2.      Repeat steps 3 and 4 while BEG ≤ END and DATA [MID] ≠ ITEM.

3.                              If ITEM < DATA[MID], then:

Set END := MID - 1.

Else:

Set BEG := MID + 1.

`                      [End of If structure.]

4.      Set MID := INT ((BEG + END)/2). [End of Step 2 loop]

5.       If DATA [MID] = ITEM, then: Set LOC := MID.

Else:

Set LOC := NULL.

[End of If structure]

6.      Exit.