MrainW's Home

All things come to those who wait!

0%

Binary search

Posted on In ,
Symbols count in article: 7.4k Reading time ≈ 7 mins.

Template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int start = 0, end = nums.length - 1;
    //adjent, [1,2] [3,4]
    while (start + 1 < end) {
        int mid = start + (end - start) / 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;
}

Type

  • Random position of the target
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
public class Solution {
    public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

  • First position of target
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
class Solution {
    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}
  • Last position of target
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
public class Solution {
    public int lastPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                start = mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[end] == target) {
            return end;
        } else if (nums[start] == target) {
            return start;
        } else {
            return -1;
        }
    }
}

Example

  • Search In a Big Sorted Array (Can not find the upper bound)

Exponential Backoff

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Public int searchBigSortedArray(ArrayReader reader, int target) {
    int kth = 1;
    while (reader.get(kth - 1) < target) {
        kth = kth * 2;
    }
    int start = 0, end = kth - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (reader.get(mid) < targrt) {
            start = mid;
        } else {
            end = mid;
        }
        if (reader.get(start) == target) {
            return start;
        }
        if (reader.get(end) == target) {
            return end;
        }
        return -1;
    }
}
  • Find K Closest Elements
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
36
37
38
39
40
41
42
43
44
45
public int[] kClosestNumbers(int[] A, int[] target, int k) {
    //A[right] >= target, A[left] < target 
    int right = findUpperCloest(A, target);
    int left = right - 1;
    int[] results = new int[k];
    for (int i = 0; i < k; i++) {
        if (isLeftCloser(A, target, left, right)) {
            results[i] = A[left];
            left--;
        } else {
            results[i] = A[right];
            right++;
        }
    }
    return results;
}
private int findUpperCloest(int[] A, int target) {
    //the 1st number >= target
    int start = 0, end = A.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] >= target) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (A[start] >= target) {
        return start;
    }
    if (A[end] >= target) {
        return end;
    }
    return A.length;
}
private boolean isLeftCloser(int[] A, int target, int left, int right) {
    //越界
    if (left < 0) {
        return false;
    }
    if (right >= A.length) {
        return true;
    }
    return (target - A[left] <= (A[right] - target));
}
  • Maximum Number in Mountain Sequence

12345654321

if have repeated number cannot use this method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int mountainSequence(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
            
        // find first index i so that nums[i] > nums[i + 1]
        //OOOOOXXXX, find first X
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            // mid + 1 保证不会越界
            // 因为 start 和 end 是 start + 1 < end
            if (nums[mid] > nums[mid + 1]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        return Math.max(nums[start], nums[end]);
    }
}
  • Find Minimum in Rotated Sorted Array

0 1 2 4 5 6 7 -> 4 5 6 7 0 1 2

-> 右边第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length - 1;
        //find first element <= target
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > nums[end]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return Math.min(nums[start], nums[end]);
    }
}

follow up: [111111110111], repeated number O(n), can not be logn

  • Search in Rotated Sorted Array

Solution 1 : find minimum first(two binary search)

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
36
37
38
39
40
41
42
43
44
45
46
public int search(int[] A, int target) {
    if (A == null || A.length == 0) {
        return -1;
    }
    int index = findMinIndex(A);
    //the target in the right part
    if (A[index] <= target && target <= A[A.length - 1]) {
        return binarySearch(A, index, A.length - 1, target);
    }
    return binarySearch(A, 0, index - 1, target);
}
private int findMinIndex(int[] A) {
    int start = 0, end = A.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] < A[end]) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (A[start] < A[end]) {
        return start;
    }
    return end;
}
private int binarySearch(int[] A, int start, int end, int target) {
    if (end < 0) {
        end += A.length;
    }
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] < target) {
            start = mid;
        } else {
            end - mid;
        }
        if (A[start] == target) {
            return start;
        }
        if (A[end] == target) {
            return end;
        }
        return -1;
    }
}

Solution 2, directly cut

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
public int search(int[] A, int target) {
    if (A == null || A.length == 0) {
        return -1;
    }
    int start = 0, end = A.lenghth - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] >= A[start]) {
            if (A[start] <= target && target <= A[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        } else {
            if (A[mid] <= target && target <= A[end]) {
                start = mid;
            } else {
                end = mid;
            }
        }
    }
    if (A[start] == target) {
        return start;
    }
    if (A[end] == target) {
        return end;
    }
    return -1;
}
  • Non sorted array

Find peak element(any peak)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findPeak(int[] A) {
    int start = 1, end = A.length - 2;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        //left high go left
        if (A[mid] < A[mid - 1]) {
            end = mid;
        } else if (A[mid] < A[mid + 1]) { //right high go high
            start = mid;
        } else {
            return mid;
        }
    }
    if (A[start] < A[end]) {
        return end;
    } else {
        return start;
    }
}
  • wood cut

有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。给定L和k，你需要计算能够得到的小段木头的最大长度。

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
36
37
38
39
public int woodCut(int[] L, int k) {
    if (L == null || L.length == 0) {
        return 0;
    }
    long maxValue = 0, sumValue = 0;
    for (int i = 0; i < L.length; i++) {
        sumValue += L[i];
        maxValue = Math.max(maxValue, L[i]);
    }
    //log(min)
    int start = 1, end = (int)Math.min(maxValue, sumValue / k);
    if (start > end) {
        return 0;
    }
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (getPieces(L, mid) >= k) {
            start = mid;
        } else {
           end = mid;
        }
    }
    if (getPieces(L, end) >= k) {
        return end;
    }
    if (getPieces(L, start) >= k) {
        return start;
    }
    return 0;
}
//O(n)
private long getPieces(int[] L, int length) {
    long result = 0;
    for (int i = 0; i < L.length; i++) {
        result += L[i] / length;
    }
    return result;
}
//O(nlog(min))

Welcome to my other publishing channels