• Sorted (monotonically increasing or decreasing)
  • Bounded (exist upper and low bounds)
  • Accessiblee by index (can be accessed by index)

all template return index in an array

Find peak template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid =  left + (right - left)/2;
            if(nums[mid] < nums[mid +1]){
                left = mid + 1;
            }else if(nums[mid] >= nums[mid + 1]){
                right = mid;
            }
                
        }
        return left;
}

Find least template

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int findLeastInValleyArray(int[] arr){
        int left =0;
        int right = arr.length-1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(arr[mid] > arr[mid+1]){
                left = mid +1;
            }else if(arr[mid]<= arr[mid+1]){
                right= mid;
            }
        }
        return left;
}

if requires to find K closet element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // Initialize binary search bounds
        int left = 0;
        int right = arr.length - k;
        
        // Binary search against the criteria described
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // Create output in correct format
        List<Integer> result = new ArrayList<Integer>();
        for (int i = left; i < left + k; i++) {
            result.add(arr[i]);
        }
        
        return result;
        
    }

Find number template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_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) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

Find left border template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

Find right border template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}