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.
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
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.
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
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.
Replies
-
Deepika BansalComplexity 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:-
- 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.
- 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.😀 -
PensuThis 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.
You are reading an archived discussion.
Related Posts
Can someone post the selection process in caterpillar?
I could not find out the previous year placement papers of caterpillar.
Please share some of the questions in this thread.
Thanks to the advancement in the technology and the simultaneous growth of human knowledge, technology does not seem safe anymore. One of the leading blogging tool and publisher tool, WordPress...
Hi Guys,
I am person not on java platform still I have to develop J2ME application which has became mandatory for me , so please can you tell any j2me...
thu 5:26 ​i am using the windows 7 to my sys
from last 1week i got the error message when i am trying to open the my sys...
we are organizing a inter-college cultural & technical fest .I gotta coordinate my college's annual techfest this year. this cosists of events like tech & science quiz , robotics events...