Binary Search

Algorithm

Given a sorted list:

1. Select the element in the middle of the list.
2. Compare the middle element to the element to be searched
   1. If the element is smaller than the middle element, repeat at 1. with left partition.
   2. If the element is greater than the middle element, repeat at 1. with right partition.
   3. If the element is equal to the middle element, the element has been found so stop.

Performance

• Worst case:
• Best case:
• Average case:
• Space complexity:

Implementations

• LSL
• C#
• ARexx