• Deepika

MemberAug 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).

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.
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies
• MemberAug 3, 2011

Complexity of this algorithm:- Complexity of binary search is same for worst and average case which is- log n with base 2.
This complexity can be derived using the 'Recursion Tree' Method since binary search uses divide and conquer technique to solve the problem.

Limitataions of this algorithm:- Binary Search is a very efficient algorithm since it requires only about 20 comparisons with an initial list of 1,000,000 elements. But it require two conditions:-
1. List must be in sorted order. But keeping a sorted array is normally very expensive when there are many insertions and deletions. Then we use linked lists, binary search trees etc to store data.
2. And secondly, we need a direct access to the middle element. But this is also not possible everytime as in case of linked list where we can't directly access the middle element.

PS: Queries and more explanation is welcome.😀
Are you sure? This action cannot be undone.
• MemberAug 4, 2011

This search is very much effective with small number of elements. But as the number increases, the space complexity increases. As u said we have to keep an array for all those elements, and we cant use linked list.
Are you sure? This action cannot be undone.