1장에서는 전형적인 배열에서 특정 값을 검색하는 과정, 즉 원하는 값을 찾을 때까지 왼쪽에서 오른쪽으로 한 번에 한 셀씩 확인하는 방법을 설명했다. 이러한 과정을 선형 검색이라 불렀다.

전형적인 배열과 정렬된 배열에서 선형 검색이 어떻게 다른지 보자.

[17, 3, 75, 202, 80]이라는 일반적인 배열이 있다고 하자. (배열에 없는) 22라는 값을 찾으려면 22가 배열 어디든 있을 수 있으므로 모든 원소를 하나도 빠짐없이 검색해야 한다. 배열의 끝에 도달하기 전에 검색을 멈추는 경우는 원하는 값을 찾았을 때뿐이다.

하지만 정렬된 배열에서는 값이 배열에 들어있지 않을 때 검색을 더 빨리 멈출 수 있다. 정렬된 배열 [3, 17, 75, 80, 202]에서 22를 찾는다고 하자. 75에 도달하면 더 이상 22가 오른쪽에 있을 수 없으므로 바로 검색을 중단할 수 있다.

다음은 루비로 구현한 정렬된 배열의 선형 검색이다.

def linear_search(array, search_value)
    
    # 배열의 모든 원소를 순회한다.
    array.each_with_index do |element, index|
        
        # 원하는 값을 찾으면 그 인덱스를 반환한다.
        if element == search_value
            return index
        
        # 찾고 있던 값보다 큰 원소에 도달하면
        
        # 루프를 일찍 종료할 수 있다.
        elsif element > search_value
            break
        end
    end
    
    # 배열에서 값을 찾지 못하면 널을 반환한다.
    return nil

end