Write a VB program for binary search?

Answer 1

The optimal binary search algorithm uses a sorted array as the data container. Define the range to be searched using a half-closed range of indices [begin:end). Initially, this will be the half-closed range of the whole array.

The algorithm is as follows:

If begin>=end, this would indicate the range is empty or invalid, thus the value cannot exist. We return the end iterator to indicate value not found.

If the range has one or more elements, then we calculate the middle index of the range:

middle = begin + (end - begin) / 2

Note: division takes precedence over addition.

We then compare the value in the middle of the range with the value being searched. If they are equal, we are done, we simply return the middle index.

Otherwise, if the value being searched is less than the middle value, we adjust the upper bound of the array so the next iteration only searches the lower half of the original range:

new_end = middle

Otherwise we adjust the lower bound of the array so the next iteration only searches the upper half of the range:

new_begin = middle + 1

We then repeat the algorithm using the adjusted half-closed range.

The algorithm can be implemented in Visual Basic as follows. Note the array, a, is passed by reference (ByRef) to prevent making an unnecessary copy of the array. The function does not make any changes to the array itself so there's no need to copy it.

Function bin_search (ByRef a As Integer(), ByVal begin As Integer, ByVal end As Integer, ByVal value As Integer) As Integer

' save the end iterator (it may change later)

Dim not_found As Integer = end

' while the range is valid...

While begin < end

' calculate middle index

Dim middle As Integer = begin + (end - begin) / 2

' compare the middle element for equality

If value = A[middle] Then

' value found!

Return middle

End If

' value not found, so determine which half of array to eliminate

If value < A[middle] Then

' eliminate upper half (if value exists, it must be in the lower half)

end = middle

Else

' eliminate lower half (if value exists, it must be in upper half)

begin = middle + 1

End If

' repeat algorithm...

End While

' if we get this far, the range is either empty or invalid (begin>=end), so the value does not exist

Return not_found

End Function

Answer 2

dim a as integer