Search First/Last Position

Search Any Position (LC.457)

Find any position of a target number in a sorted array. Return -1 if target does not exist.

Example

Input: [1, 2, 2, 4, 5, 5], target = 2
Return: either 1 or 2
Input: [1, 2, 2, 4, 5, 5], target = 6
Return: -1

Analysis

This is the vanilla binary search. We can use a no-brainer template. Here we will go over details and understand how this template was made. Oh and the brute force approach is just to scan the array and find the target.

While Loop

For any array question, we first check for the null/empty input. We want to set the base case as start and end next to each other. The merit of this approach is not very clear at this stage. But later we will see why this is very helpful. If the median < target, search the right section. If the median > target, search the left section. Solve the base case in the end.

public classicBS(int A[], target) {
    if (A == null || A.length == 0)
        return -1;
    int start = 0, mid, end = A.length - 1;
    // stop when start and end next to each other
    while (start + 1 < end) {
        // mid = (start + end) / 2; might overflow
        mid = start + (end - start) / 2;
        if (A[mid] == target) {
            return mid;
        } else if (A[mid] < target) {
            // median is less than target, search in the right section
            start = mid + 1;
        } else {
            // median is bigger than target, search in the left section
            end = mid - 1;
        }
    }
    // start is next to end now
    if (A[start] == target) {
        return start;
    } else if (A[end] == target) {
        return end;
    } else {
        return -1;
    }
}

Recursion

This might feel more natural to write but again recursion needs space on call stack to work. When the number is large enough, we might encounter stack overflow.

public int findPosition(int[] A, int target) {
    if (A == null || A.length == 0) {
        return -1;
    }
    return bsHelper(A, target, 0, A.length -1);
}

private int bsHelper(int[] A, int target, int start, int end) {
    // base case
    if (start + 1 >= end) {
        if (A[start] == target) {
            return start;
        } else if (A[end] == target) {
            return end;
        } else {
            return -1;
        }
    }
    // decrease
    int mid = start + (end - start) / 2;
    // conquer
    if (A[mid] == target) {
        return mid;
    } else if (A[mid] < target) {
        // the median < target, search right section
        // +/-1 since mid is not the target
        return bsHelper(A, target, mid + 1, end);
    } else {
        // the median > target, search left section
        return bsHelper(A, target, start, mid - 1);
    }
}

Search First Position (LC.14)

Given a sorted array and a target, find the first occurrence of this target.

Example

Input: [1, 2, 2, 4, 5, 5], target = 2
Return: 1 (not 2)

Analysis

Now we see why we need to make our base case where start and end next to each other. For this question, we only have to change when A[mid] == target, end = mid.

Code

// first position of target
// don't return mid when == target, set end = mid
public firstPosition(int A[], target) {
    if (A == null || A.length == 0)
        return -1;
    int start = 0, mid, end = A.length - 1;
    // stop when start and end next to each other
    while (start + 1 < end) {
        // mid = (start + end) / 2; might overflow
        mid = start + (end - start) / 2;
        if (A[mid] == target) {
            end = mid;
        } else if (A[mid] < target) {
            // median is less than target, search in the right section
            start = mid + 1;
        } else {
            // median is bigger than target, search in the left section
            end = mid - 1;
        }
    }
    // start is next to end now
    if (A[start] == target) {
        return start;
    } else if (A[end] == target) {
        return end;
    } else {
        return -1;
    }       
}

Search Last Position (LC.458)

Given a sorted array and a target, find the last occurrence of this target.

Example

Input: [1, 2, 2, 4, 5, 5], target = 2
Return: 2 (not 1)

Analysis

When A[mid] == target, start = mid. For the base case, check A[end] == target first.

Code

// last pos of target
// set start = mid, return end first after while loop
public firstPosition(int A[], target) {
    if (A == null || A.length == 0)
        return -1;
    int start = 0, mid, end = A.length - 1;
    // stop when start and end next to each other
    while (start + 1 < end) {
        // mid = (start + end) / 2; might overflow
        mid = start + (end - start) / 2; // notice write <= might get bug easily
        if (A[mid] == target) {
            start = mid;
        } else if (A[mid] < target) {
            // median is less than target, search in the right section
            start = mid + 1;
        } else {
            // median is bigger than target, search in the left section
            end = mid - 1;
        }
    }
    // start is next to end now
    if (A[end] == target) {
        return end;
    } else if (A[start] == target) {
        return start;
    } else {
        return -1;
    }       
}

Conclusion

The most transparent binary search question follows this format: We can check(A[index]) = {T, F}, then the array becomes [T, T, T, T, T, F, F, F, F, F]. We want to find the last T or the first F or in between.