Binary Search Algorithm
The principle of a binary search can be generalized to any type of problem provided the elements of the search can form a sorted list or sequence and it is possible to make a comparison on the order in the sequence.
Playing the number game: Say we have a number range from 0 to 100, and now you have to pick the number I’m thinking of and depending on your guess ill answer with either “correct”, “higher” or “lower”. What number would you choose? The binary search provides the quickest solution to this problem; the number you should choose is 50.
The binary search algorithm is one of the most efficient methods for locating the position of an element in a sorted list. The way it functions is by going straight to the middle of the list and checking whether the value is greater than, less than or equal to the element it's looking for. If equal to, then the element has been found, if not, then the algorithm eliminates half the list from consideration, and repeats the procedure on the remaining half. Thus, the number of elements needing to be checked is halved each time.
So, back to the number game: Why was “50” the best guess? Well in the best case your guess is correct, I was thinking of the number 50. In the worst case you’ll either get a “Higher” or “Lower”. Now think about the following, if you got “Higher” you eliminated numbers 0-49, or if you got “Lower” you eliminated 51-100, in other words, either way you eliminate HALF the possibilities. Now, let’s say my response was “Higher”. What would you guess after? 75. Since it’s in between 50 – 100. If you didn’t guess correctly, you’ll be facing the similar scenario as before. You’ll end up eliminating half the possibilities and eventually guessing correctly (assuming of course the number I was thinking of is within the bounds 0-100)
In computer programming terms, the algorithm operates on an ordered list of values and uses the order to conduct the search. So, for a list or array containing a large amount of elements the binary search will, on average, out-perform a linear search - in a list of one million items, a linear search will take an average of 500,000 comparisons to find a particular item. A binary search will take a maximum of 20. Pretty impressive huh. Beware though, as the search only works on a sorted list, if the list requires sorting first and only has a few elements then it may be faster to perform a linear search than to sort the list and then perform a binary search.
Implementing the algorithm in code is possible through recursion and it can also be implemented iteratively.
The .Net framework offers a BinarySearch method in it collection base classes. You can perform this method on a sorted array or collection. One of the most useful cases is when you have a generic list of objects or classes (Collections.Generic.List(Of T)) and you need to find a particular element, this can be done as shown in example 1 below.
1) Implementation Of Binary Search - Source Code Example (asp.Net):
Public Class contact
Public name As String
Public address As String
Public number As String
Public Sub New(ByVal txtname As String, ByVal txtaddress As String, ByVal txtnumber As String)
Me.name = txtname
Me.address = txtaddress
Me.number = txtnumber
End Sub
Public Class sortByName
Implements IComparer(Of contact)
Public Function Compare(ByVal x As contact, ByVal y As contact) As Integer Implements System.Collections.Generic.IComparer(Of contact).Compare
'then return the comparison on the names
If x.name = y.name Then
Compare = x.name < y.name
Else
Compare = x.name > y.name
End If
End Function
End Class
End Class
Public Class managecontacts
Dim indexPosition As Integer
Dim contacts As New Collections.Generic.List(Of contact)
Public Sub manipulateContacts(ByVal elementToFind As contact)
contacts.Add(New contact("John", "123 Fake St", "123123123"))
contacts.Add(New contact("James", "124 Fake St", "123123654"))
contacts.Add(New contact("Jane", "125 Fake St", "123123987"))
contacts.Sort(New contact.sortByName)
Dim position As Integer = contacts.BinarySearch(0, contacts.Count, elementToFind, New contact.sortByName)
If position < 0 Then
'item is not in list
Exit Sub
Else
'found item
indexPosition = position
End If
End Sub
End Class
If your the type of programmer who likes to get into the nitty gritty details i've implemented a custom binary search below as well (example 2), feel free to implement it/pick holes in it/come up with a better solution and post your findings.
2) Custome Binary Search - Source Code Example (asp.Net):
Public Function doBinarySearch(ByVal X As Object, ByVal list As Object) As Integer
'Binary Search
'To begin with, the span to be searched is the full supplied list of elements, as marked by variables L and R
'The initialisation of L and R to 0 and N + 1
Dim L, R, N, p As Integer
Dim foundItem As Boolean = False
N = list.Count
L = 0
R = N + 1
Do Until foundItem
p = (R - L) / 2
Select Case p
Case Is <= 0
'return "Not Found"
Exit Do
Case Is > 0
'p = L + p which by construction is within the bounds (L + 1) to (R − 1)
p = L + p
Select Case list(p).itemCode & list(p).cityCode
Case X
'return "Success"
foundItem = True
Case Is < X
L = p
Case Is > X
R = p
End Select
End Select
Loop
End Function
enjoy!!!