Algorithm Pattern – Binary Search

Algorithm Pattern 1 – Find the target element

class Solution {
    public int search(int[] nums, int target) {

        int left = 0, right = nums.length - 1;

        while(left <= right){
            int mid = left + (right - left) / 2;

            if(nums[mid] == target){
                return mid;
            }

            else if(nums[mid] < target){
                left = mid + 1;
            }

            else if(nums[mid] > target){
                right = mid - 1;
            }
        }

        return -1;
    }
}

Detail Reflection

1. Why "while(left <= right)"

   Because we set right as "nums.length – 1", it is a valid index, not like "nums.length". Therefore, the search range should be left closed and right closed, the case, when "left == right", it means there exist one element in the search range, we have to consider this case.

   If we really want to write it as "while(left < right)", we should change the return statement as "return nums[left] == target ? Left : -1" to check if the search range we skipped is the correct answer.

2. Why "left = mid + 1" and "right = mid – 1"

   Based on what we have discussed above, the search range is a closed range. So when we consider the index update, we should not consider the current checked index anymore.

Algorithm Pattern 2 – Find the left boundary

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; 

    while (left < right) { 
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; 
        }
    }
    return left;
}

Detail Reflection

1. Why "while(left < right)"

   Because we set right as "nums.length", it is an invalid index, so the search range is actually left closed right open. Therefore if the search end in the tail as "left == right", we should not consider this index.

2. Why don’t "return -1", what if no such element exists in array?

   The left range would be [0, nums.length]. We could also change our return statement as:
   If(left == nums.length) return -1;
   Return nums[left] == target ? Left : -1;

Change Pattern 2 to Pattern 1

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

Algorithm Pattern 3 – Find the right boundary

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }

if(left ==0)return-1;
Return nums[left-1]==target ?(left-1):-1;

}

Change Pattern 3 to Pattern 1

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            left = mid + 1;
        }
    }
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}