Question

2. Write an algorithm called locate (with running time log n, that accept a set of integer numbers and another single number and finds out whether the number is found in the set of integers. If it exist, it should print its index in the list otherwise should print negative one (-1).

Answer 1

Array should be sorted before running this function. Otherwise it is impossible to find a key in array with running time log(n).

program locate(array A, key)
    imin = 0;
    imax = length of A;
    // continue searching while [imin,imax] is not empty
    while imax >= imin
        // calculate the midpoint for roughly equal partition
        imid = (imin + imax) / 2;
        // determine which subarray to search
        if A[imid] < key
            // change min index to search upper subarray
            imin = imid + 1;
        else
            if A[imid] > key
                // change max index to search lower subarray
                imax = imid - 1;
            else
                // key found at index imid
                print imid;
    // key not found
    print -1;