PcoWSkbVqDnWTu_dm2ix
We use cookies on this site to enhance your user experience

Jul 02 2018, 5:43 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
  3. If it is, then jump to the right. Otherwise, jump to the left
  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:

Binary_Search_Image.png

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