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:
- Sort the list if it is not already sorted. Binary search will not work on unsorted lists.
- Find the middle item in the set (list.length / 2).
- Compare this item to the search item.
- If it is the item you are looking for, you are done.
- If it is not, determine if the search item comes before (left) or after (right) the middle element.
- If it comes before, split the list in half to the left of the middle item.
- If it comes after, split the list in half to the right.
- 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.
- Use a while loop
- 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.
- 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.
- High or Right = right index value.
- Initially set to list.length-1.
- Set to Mid – 1 if search < list[Mid] while looping
- Low or Left = left index value.
- Initially set to zero.
- Set to Mid + 1 if search > list[Mid] while looping
- Mid = middle value.
- This is the value that you compare to search.
- Initially set to (( list.length – 1 ) / 2) or below.
- Set to (Left + Right) / 2 while looping
- High or Right = right index value.
- Kick out when
- Search == list[Mid]
- Not found. Using Left and Right, how will you know when the value is not found?
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!
Advantages and Disadvantages
- Very efficient at finding elements in a sorted array.
- The array must be sorted.
- Can be tricky to code.
Other Resources
Edhesive T2 Lesson 17: Binary Search
AP College Board Video: Binary Search
Geeks for Geeks: text explanation