lower/upper bound

定义 lower bound 为在给定升序数组中大于等于目标值的最小索引，upper bound 则为小于等于目标值的最大索引.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
* nums[index] >= target, min(index)
* in another word: return the smallest index of nums[index] that >= target
*/
public static int lowerBound(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    int lb = -1, ub = nums.length;
    while (lb + 1 < ub) {
        int mid = lb + (ub - lb) / 2;
        if (nums[mid] < target) {
            lb = mid;
        } else {
            ub = mid;
        }
    }
    return lb + 1;
}
/*
* nums[index] <= target, max(index)
* in another word: return the largest index that nums[index] <= target
*/
public static int upperBound(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    int lb = -1, ub = nums.length;
    while (lb + 1 < ub) {
        int mid = lb + (ub - lb) / 2;
        if (nums[mid] > target) {
            ub = mid;
        } else {
            lb = mid;
        }
    }
    return ub - 1;
}

first/last occurrences

Last occurrence:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    /**
     * @param nums: An integer array sorted in ascending order
     * @param target: An integer
     * @return an integer
     */
    public int lastPosition(int[] nums, int target) {
        // Write your code here
        if(nums == null || nums.length == 0){
            return -1;
        }
        
        int start = 0;
        int end = nums.length -1;
         //[1,2,2,4,5,5] 2
        while(start + 1 < end){ // exit when start + 1 >= end thus when start == end - 1
            int mid = (start+end)/2;
            if(nums[mid] < target){
                start = mid;
            }else if(nums[mid] > target){
                end = mid;
            }else{
                start = mid;//这里不用return mid;而是采取赋值缩小范围
            }
        }
        
        if(nums[end] == target){
            return end;
        }
        if(nums[start] == target){
            return start;
        }
        return -1;
    }
}

First occurrence:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearchForFirstOccurrence(int[] nums, int target) {
        //write your code here
        if(nums == null || nums.length ==0){
            return -1;
        }
        
        int start = 0, end = nums.length -1;
        while(start+1<end){
            int mid = (start+end)/2;
            if(nums[mid] < target){
                start = mid;
            }else if(nums[mid] > target){
                end = mid;
            }else{
                end = mid;
            }
        }
        
        if(nums[start] == target){
            return start;
        }
        if(nums[end] == target){
            return end;
        }
        
        return -1;
    }
}