정렬된 배열인 경우 Binary Search를 통해 O(log N)의 속도 신속하게 검색할 수 있다. 이 문제는 그러나 시작 위치가 배열내 임의의 위치에 있다라고 했으므로, 이진 검색 방식을 약간 변형해야 한다. 즉, 이진 검색에서 중간값보다 클 때, 마지막 오른쪽 바운더리 값과 다시 비교하여 해당 k값이 오른쪽 범위에 존재하는지 다시 체크해야 한다. 왜냐하면 큰 값이 왼쪽에 있을 수 있기 때문이다. 이러한 방식으로 중간값보다 작은 경우도 다시 왼쪽 바운더리를 체크한다. 이렇게 추가적인 바운더리 체크가 있다 하더라도, 이진 검색 방식으로 중간 값을 계속 체크한다는 점은 동일하다.

public void RunTest()
{
    int[] A = { 17, 19, 21, 4, 8, 10, 11 };
    int index = SearchInArray(A, 0, A.Length - 1, 19);
    Console.WriteLine(index);
}

public int SearchInArray(int[] A, int left, int right, int k)
{
    if (left > right)
        return -1;

    int mid = (left + right) / 2;
    if (k == A[mid])
        return mid;
            
    if (k > A[mid])
    {
        if (k <= A[right])
            left = mid + 1;
        else
            right = mid - 1;
    }
    else // k < A[mid]
    {
        if (k >= A[left])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return SearchInArray(A, left, right, k);
}