2.1 Binary Search (Basic)

Logical Steps

Continuously look for mid ( (start + end) / 2 ) and compare with target (while start + 1 < end)

1. If target is greater, move start to mid to eliminate smaller part; if target is smaller, move end to mid; if target = mid, return mid
2. We get start and end eventually, when start + 1 = end, target can be either start or end. If we look for first occurrence, start with comparing start, if look for last occurrence, start with looking at end

Code Template

// make sure start = end -1 after exit loop
while (start + 1 < end) {
    int mid = (start + end)/2;

    // continuously look for mid and compare with target
    if (target > A[mid]){
        start = mid;
    }else{
        end = mid;
    }
}

// now we have start = end-1, target could be in these two,
// or not
if (target == A[start]){
    return start;
}else if (target == A[end]){
    return end;
}

// if not, return -1
return -1;

Common Mistake

1. Use mid = target for comparison instead of A[mid] == target
2. When target = mid, return mid directly

    /** this is a mistake example
    * when there is multiple value = target, we should return 
    * first matching position, that is to say,
    * when target == mid
    * we should let end = mid instead of return mid directly
    */
    if (A[mid] == target){
        return mid;
    }else if (target > A[mid]){
        start = mid;
    }else{
        end = mid;
    }