Question: I have a mtd to search through 1mil or more records (stored as an arraylist of integers in asc order) to check if the pass in empID belongs to one of the records stored.

Currently, i uses sequential search through for loop. How to make it more efficient/faster? 

```
def exist?(id)
    for i in 0...$employee_list.length
        if $employee_list[i] == id # match!
            return true
        elsif $employee_list[i] > id # have already gone beyond the point where id should've been found
            return false
        end
    end

return false # cannot find id in the list
end

```

I also tried using hash as follows but still not fast enough.

```
hash = $employee_list.map{ |i | i}

if hash.include? id
    return true 
else
    return false
end

```

Answer: 
Use a `Set`, unless you have proven that you cannot afford the memory:

```
# Do this just once
require 'set'
$employee_ids = Set.new $employee_list

# Do this each time you need to check
def exist?(id)
  $employee_ids.include?(id)
end

```

It will be nearly instantaneous, regardless of the number of ids you have.
Try this

```
array.bsearch {|x| number <=> x }

```

This does a binary search on the array. The array MUST be sorted.

Note that the element `x` is to the right side of the spaceship operator!

Use the `ri` command to read more documentation on the `bsearch` method. The time complexity of binary search is `O(log n)`. Which is 20 steps only for an array of length 1 million.