# Binary Search

Jun 14 2019, 2:12 PM PST 5 min

Binary Search is a very famous and efficient Data Searching algorithm for sorted arrays. Rather than going through each item in the array like the Linear Search algorithm, it jumps around the array to efficiently find the search query. One trade-off with this algorithm will work “only” on sorted arrays. To automatically sort the array, use the table.sort function.

### Procedure

1. Start at the middle of the table. Check to see if that value matches the query
2. If it does, return it. If not, check to see whether the query is greater or less than the current value
4. Repeat steps 2-4 until you get a match (or return -1 if you find no matches)

For example, let’s say we want to find 8 in a list of 1, 3, 5, 7, 8, 9, and 11. First, we get the middle value, which is 7 in this case. Since 8 is greater than 7, we go to the right to 9, because nine is in the middle between where 7 is an the end of the array. Now, nine is greater than 8, so we go halfway between where nine is and seven is, which is just one over- and that number also happens to be 8, which means we’ve finally found it.
That whole process can be shown like this: ### Implementation

```function search(data, query)
-- Set the left and right boundaries
local left = 1
local right = #data
while left <= right do
-- Get the middle value, between the left and right boundaries
local middle = math.floor((left + right) / 2)
if data[middle] == query then
-- We found it, now we return it
return middle
elseif data[middle] > query then
-- Change the right boundary
right = middle - 1
else
-- Change the left boundary
left = middle + 1
end
end
-- The query wasn't found in the array
end
```
```local sorted_data = {"a", "b", "c", "d"}
print(search(sorted_data, "c"))
print(search(sorted_data, "e"))
```

Outputs:

```3
nil
```
Tags:
• search
• algorithm