Binary Search Template

class Solution {
    public int search(int[] nums, int target) {
        // search range : [start, end)
        int start = 0;
        int end = nums.length;
        
        // remember loop condition: start < end,
        // will terminate if start == end;
        while(start<end){
            // mid position is righter (not important)
            int mid = (start+end)/2;
            if (nums[mid] == target) return mid;
            
            if(nums[mid] > target){
                // new range: [start, mid)
                end = mid;
            }
            else{
                // new range: [mid+1, end)
                start = mid+1;
            }
        }
        return -1;
    }
}

Divide a array (n) into two half, and the length is L

1.Start index 0, end index: L-1, middle index: L/2

If L is even, then number of elements on the left of middle: L/2 , number of elements on the right side of L: L/2-1,

If L is odd, number of elements on the left of middle point: (L-1)/2, number of elements on the right side of L: (L-1)/2

2. start index 0, end index: L-1; middle index M = (L-1)/2

if L is even: number of elements on the left of M: (L-1)/2, number of elements on the right side of M: (L-1)/2

if L is odd: number of elements on the left of M: (L-1)/2, number of elements on the right side of M: (L-1)/2+1;