Deepika

Member • Aug 3, 2011

## Binary Search Algorithm-Concept Explained

Binary Search is one way to find some element, say ITEM, in a linear (one dimensional) array which is sorted in some order. This order may be ascending or descending (considering the array to be consisting only of numeric value).

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 set LOC=NULL.

1. [Initialize segment variables.] Set BEG=LB, END=UB and MID=INT((BEG+END)/2).

2. Repeat step 3 and 4 while BEG<=END and DATA[MID]!=ITEM. [!= denoted 'not equal to']

3. If ITEM 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.

**Technique:-**Consider that our array (DATA) is sorted in ascending order. In this algorithm, we compare the ITEM with the middle element (element at the middle index) of the array.- If both of them match, then we'll simply print the middle location of the array.
- If they don't match, then we'll compare if the ITEM is less than or greater than the middle element.
- If ITEM is less than the middle element, then we'll shift to the list which is to the left of the middle element (because the left list contains the numbers smaller than the middle element).
- Similarly, if ITEM is greater than the middle element, then we'll shift to the right list because the right list contains the element greater than the middle element.
- With this process, we've divided our array into two smaller list.
- And we now have to search for the ITEM in just half of the list through the above process.
- So we'll put this whole of the process in loop and at the end, we'll have our result.

**Algorithm:-****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 set LOC=NULL.

1. [Initialize segment variables.] Set BEG=LB, END=UB and MID=INT((BEG+END)/2).

2. Repeat step 3 and 4 while BEG<=END and DATA[MID]!=ITEM. [!= denoted 'not equal to']

3. If ITEM 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.