Allan Didier

Computer Science Teacher

# Binary Search Explanation

#### Description

Binary search is an algorithm for faster searching than Linear Search. It requires a sorted list, though. Basically, you cut the list in half, looking at the middle item for your search item. You continue doing so until you find what you are looking for. Click here for the Binary Search assignment.

#### Logic

The basic logic of the binary search algorithm goes as such:
1. Sort the list if it is not already sorted. Binary search will not work on unsorted lists.
2. Find the middle item in the set (list.length / 2).
3. Compare this item to the search item.
4. If it is the item you are looking for, you are done.
5. If it is not, determine if the search item comes before (left) or after (right) the middle element.
6. If it comes before, split the list in half to the left of the middle item.
7. If it comes after, split the list in half to the right.
8. Repeat the process by looking at the middle element in the new half of the list.

#### Coding

This can be done using loops or can be done recursively. I will not discuss the recursive way since we have not talked about recursion, yet.
1. Use a while loop
1. While not found ( search != list[i] ) continue. You also need a check to kick out of the loop if the search is not actually in the list.
2. Use three variables to keep track of indices of where you are searching in your array. Remember, index values are integers and are rounded down when divided unevenly.
1. High or Right = right index value.
1. Initially set to list.length-1.
2. Set to Mid – 1 if search < list[Mid] while looping
2. Low or Left = left index value.
1. Initially set to zero.
2. Set to Mid + 1 if search > list[Mid] while looping
3. Mid = middle value.
1. This is the value that you compare to search.
2. Initially set to (( list.length – 1 ) / 2) or below.
3. Set to (Left + Right) / 2 while looping
3. Kick out when
1. Search == list[Mid]

#### Example

• Array (10 elements): 8, 13, 20, 31, 45, 52, 55, 62, 78,  98
• Search for 20
• First pass: left = 0, right = 9, mid = 4; 20 < 45.
• Second pass: left = 0, right = 3, mid = 1, 20 > 13
• Third pass: left = 2, right = 3, mid = 2, 20 == 20, found!
• Search for 19
• First pass: left = 0, right = 9, mid = 4; 19 < 45.
• Second pass: left = 0, right = 3, mid = 1, 19 > 13
• Third pass: left = 2, right = 3, mid = 2, 19 < 20
• Fourth pass: left = 2, right = 1. mid = 1.  Not found!