Binary Search

If our data is pre-sorted then a binary search starts to make a lot of sense. It is like the guessing game we mentioned earlier where you need to find a number between 1 and 100. No one asks for 1, then 2, then 3… until they find it.

Instead we ask for the mid point, and then find out if we are higher or lower, and with each pass we eliminate 50% of the remaining elements.

This is the same idea for a binary search. If you search a sorted array, you can find the elements faster by eliminating 50% of the remaining elements until you find your actual item.

This is relatively fast to code, especially if you are using recursion, however, you can also code it using a loop if you want.

Function FindElement(Array, SearchItem, Low, High)
Index = Int((Low + High) / 2)
    If Array[index] == SearchItem Then
        Return SearchItem
    Else
        If Array[Index] < SearchItem Then
            FindElement(Array, SearchItem, Low, Index)
        Else
            FindElement(Array, SearchItem, Index, High)
        End If
    End If
End Function

For fun: – can you rewrite this as a while loop? Hint: Yes, you can – now try to.

Now, should you have multiple sorted arrays based upon the elements that you and your users commonly search for? Maybe. Pointers to an object are relatively cheap from a computing perspective. However, you probably cannot have a sorted array for every possible item and sub-item.

If this looks familiar, it is probably because you are thinking of a binary tree. A binary tree serves a similar purpose, allowing you to navigate down a series of nodes which eliminates about half of the remaining node each tome you move. Now with a random sorted array, you remove exactly half, but you now have to have that array in contiguous memory space.

Binary Search was originally found on Access 2 Learn