Binary Search Template

Posted on | In

Template left+1 < right: Finding Position of Target

Example Given nums = [1, 2, 2, 5, 7, 7].

For target = 2, return 1 or 2.

For target = 5, return 3.

For target = 6, return -1.

Template

1
2
3
4
5
6
7
while left+1 < right:
    mid = left + (right-left)/2
    nums[mid] == target ? mid
    nums[mid] < target ? left = mid
    nums[mid] > target ? right = mid
nums[left] == target
nums[right] == target

Code

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
class Main {
    public static void main (String[] args) {
        int[] nums = new int[] {1, 2, 5, 5, 6, 7, 10};
        int target = 5;
        int res = findTarget(nums, target);
        System.out.println(res); // 3
    }

    public static int findTarget(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

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

        if (target == nums[left]) {
            return left;
        }
        if (target == nums[right]) {
            return right;
        }
        return -1;
    }
}

Template left+1 < right: Find First Position of Target

Example Given nums = [1, 2, 2, 5, 7, 7].

For target = 2, return 1.

For target = 7, return 4.

For target = 6, return -1.

Template

1
2
3
4
5
6
7
while left+1 < right:
    mid = left + (right-left)/2
    nums[mid] == target ? right = mid
    nums[mid] > target ? right = mid
    nums[mid] < target ? left = mid
nums[left] == target
nums[right] == target

Code

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
class Main {
    public static void main (String[] args) {
        int[] nums = new int[] {1, 2, 2, 5, 7, 7};
        int target = 2;
        int res = findFirstTarget(nums, target);
        System.out.println(res); // 1
    }

    public static int findFirstTarget(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

        int left = 0, right = nums.length-1;
        while (left + 1 < right) {
            int mid = left + (right - left)/2;
            if (target == nums[mid]) {
                right = mid; // <-------- notice we set right=mid
            } else if (target < nums[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (target == nums[left]) {
            return left;
        }
        if (target == nums[right]) {
            return right;
        }
        return -1;
    }
}

Version 2:

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
class Main {
    public static void main (String[] args) {
        int[] nums = new int[] {1, 2, 2, 5, 7, 7};
        int target = 2;
        int res = findFirstTarget(nums, target);
        System.out.println(res); // 1
    }

    public static int findFirstTarget(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

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

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

        return -1;
    }
}

Binary Search Template

Binary Search can solve many problems that are asking for finding a particular element, and it has time complexity of $O(\log n)$.

In most cases, if a problem is asking the following, we should think about using Binary Search.

  1. The array we are going to search is sorted or partial sorted.
  2. If required time complexity is less than $O(n)$, or required $O(\log n)$.

Binary Search has many various forms. We will discuss the following:

  1. Standard Binary Search
  2. Find the target’s first position
  3. Find the target’s last position
  4. Find the target’s first and last position
  5. Find any peek element

First, we will explain the standard Binary Search template.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class BinarySearch {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
  • Loop condition: left <= right
  • Mid position: mid = left + ((right -left) >> 1)
  • Left position update: left = mid + 1
  • Right position update: right = mid - 1
  • Return value: mid or -1

Note:

  1. Our loop condition includes left == right, so in every iteration, we should update left and right position so that prevent infinity loop.
  2. Loop ending condition:
    • Found the target
    • left > right (This situation will happen if left, right, mid are pointing to the same position, but the value is not equal to target and we finish finding the entire array)
  3. left + ((right -left) >> 1) is equal to (left + right) / 2. We prefer the first form because it can prevent (left + right) > Integer.MAX_VALUE. We use right shift so the performance will improve.
  4. If the number of array is odd, left + ((right -left) >> 1) will point to the middle element; if even, it will point to left middle. Therefore, it will have below two conditions when left and right meet.
    • left/mid, right (left and mid point to the same element, right point to its next element)
    • left/mid/right point to the same element For example, in array [1, 2], left will point to 1, same as left.

Practice 1: Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

1
2
3
-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example :

1
2
Input: n = 10, pick = 6
Output: 6

We can use standard Binary Search to solve this problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + ((right-left) >> 1);
            if (guess(mid) == -1) {
                right = mid - 1;
            } else if (guess(mid) == 1) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

Practice 2: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of $x$, where $x$ is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

1
2
Input: 4
Output: 2

Example 2:

1
2
3
4
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
             the decimal part is truncated, 2 is returned.

It seems like this problem is not related to Binary Search, but we can actually use Binary Search to find a guess number, then compare if we should continue finding the left side of the guess number or right side of the guess number. For example, if we want to find the square root of 16. If we first guess 8, then compare 8 and 16/8=2, since 8 > 2, we know the target will be on the left side of 8. If we guess 5, then compare 3 and 16/3=5, since 3 < 5, we know the target will be on the right side of 3. If we guess 4, since 4 = 16/4, then we know 4 is the target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 1;
        int right = x;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (mid > x / mid) {
                right = mid - 1;
            } else if (mid < x / mid) {
                if (mid + 1 > x / (mid + 1)) return mid; // think of input x = 8
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1; // only for return a value
    }
}

// 0， 1， 2， 3， 4， 5， 6， 7， 8

In the above problem, we use mid > x / mid instead of mid * mid > xbecause we want to prevent out of mid * mid > Integer.MAX_VALUE. This is the same reason why we use left + ((right - left) >> 1) but not (left + right) / 2.

Find First Position of Target

We use Binary Search to find the first position of target, or the most left position of target if the problem include any one of the following requirement:

  1. Array is sorted, and array has duplicated number
  2. Array is partial sorted, and array does not have duplicated number
  3. Array is partial sorted, and array has duplicated number

Find First Position of Target Type 1

This type template solves the above first and second situations.

Since we are finding the most left position of the target, then theright must moving to the left side. In other words, if we find out nums[mid] == target, this mid position may not be the most left position of the target, we still neeed to find the left side. So if nums[mid] > target or nums[mid] == target, we are moving right to mid, in other words, toward the left side.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}
  • Loop condition: left < right
  • Mid position: mid = left + ((right -left) >> 1)
  • Left position update: left = mid + 1
  • Right position update: right = mid
  • Return value: nums[left] == target ? left : -1

This is different from the standard Binary Search:

First, the right position update is right = mid because when we already found the target, we want to keep find the left side of mid if other values equal to target on the left side of mid.

Next, the loop condition is left < right. Because at the end if left and right are next to each other, then mid and left will be point to the same position. Then next iteration, left, mid, and right will point to the same position. If the loop condition is changed to left <= right, then we need will have next iteration. If nums[mid] < target, then we are good, out of this loop. Else, we will have right = mid, and we didn’t change any of left, mid, right so we will have an infinity loop.

In fact, we only loop till left and right are next to each other. Because after this iteration, left, mid, and right will point to the same position. If this position’s value is equal to the target, then this position must be the most left position of the target. If it doesn’t equal to target, then it means we do not find the target in the whole array. Therefore, we have nums[left] == target ? left : -1 outside the loop.

Practice 3: First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

1
2
3
4
5
6
7
Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

Above is the problem that asking us to find the most left position of the target. We can use the template directly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (!isBadVersion(mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return isBadVersion(left) ? left : -1;
    }
}

Similar examples also include 744. Find Smallest Letter Greater Than Target and 658. Find K Closest Elements.

Practice 4: Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

1
2
Input: [3,4,5,1,2]
Output: 1

Example 2:

1
2
Input: [4,5,6,7,0,1,2]
Output: 0

This problem is the second situation. Array is partial sorted, and array does not have duplicated number. We can think of it asking us to find the original array’s most left position value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1) return nums[0];

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

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

        return nums[left];
    }
}

Find First Position of Target Type 2

This method is used in the third situation that array is partial sorted, and array has duplicated number. In this situation, when we making the right toward the left side, we can’t simply do right = mid when nums[mid] == target because there are duplicated numbers, and it will skip some numbers from mid+1 to right-1 inclusive. So, we when nums[mid] == target, we will move right only one step forward, in other words, right = right-1 when nums[mid] == target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int 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;
            } else {
                right--;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

Practice 5: Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

1
2
Input: [1,3,5]
Output: 1

Example 2:

1
2
Input: [2,2,2,0,1]
Output: 0

Note:

This problem is similar to Practice 4, but with one more condition that array may contains duplicted elements. We can use the find first position of target type 2 to solve it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1) return nums[0];
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > nums[right]) { // mid is on the left side of minimum
                left = mid + 1;
            } else if (nums[mid] < nums[right]) { // mid is one the right side of minimum
                right = mid;
            } else {
                // think of example [2,2,2,0,2]
                right--;
            }
        }
        return nums[left];
    }
}

Find Last Position of Target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1) + 1;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }
}
  • Loop condition: left < right
  • Mid position: mid = left + ((right -left) >> 1) + 1
  • Left position update: left = mid
  • Right position update: right = mid - 1
  • Return value: nums[right] == target ? right : -1

This is symmetrically written as finding the first position of target. Note that here the mid position calculation is changed, we are adding 1 behind. Now, no matter the array has odd or even number, the mid is on the right side of the middle.

When we find the most left position of the target, the mid is on the left side of the middle; if we find the most right side position of the target, the mid is on the right side of the middle. When left and right next to each other, if mid is on the left side of the middle, then left and mid point to the same position, right point to their next position. If we do not plus one at the end of the mid, in other words, the mid is on the left side of the middle, and if nums[left] == target, then the left, right, mid never change and we are in the infinity loop. Therefore, we want the mid to be on the right side of the middle, then the left can move toward the right.

Find First and Last Position of Target

We can first find the left most position of the target, then find the right most position of the target.

Practice 6: Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of $O(\log n)$.

If the target is not found in the array, return [-1, -1].

Example 1:

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if(nums == null || nums.length == 0) return res;
        // find the left-end
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        res[0] = nums[left] == target ? left : -1;

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

Find Peek Element

This type of problem is comparing the left neighbor and right neightbor.

Practice 7: Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

1
2
3
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

1
2
3
4
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
             or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

This problem asks us to find any of the local peek element, and there’s no duplicated element, and the array even is not sorted. We can solve it by comparing nums[mid] < nums[mid + 1].

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

        return left;
    }
}

Note that in this problem, we are comparing nums[mid] < nums[mid + 1], in fact, it’s checking the neighbor elements’s characteristic.

Find first greater element in a sorted array

Practice 8: Find first greater element in a sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Main {
    static int greater(int[] arr, int target) {
        int left = 0;
        int right = arr.length-1;
        while (left <= right) {
            int mid = left + ((right-left) >> 1);
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    public static void main (String[] args) {
        int[] arr = new int[] { 1, 2, 3, 5, 8, 12 };
        System.out.println(greater(arr, 8));
    }
}

Find first smaller element in a sorted array

Practice 9: Find first smaller element in a sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Main {

    static int smaller(int[] arr, int target) {
        int left = 0;
        int right = arr.length-1;
        while (left <= right) {
            int mid = left + ((right-left) >> 1);
            if (arr[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
    public static void main (String[] args) {
        int[] arr = new int[] { 1, 2, 3, 5, 8, 12 };
        System.out.println(smaller(arr, 5));
    }
}

Summary

Template Loop Condition Left Position Update Right Position Update Calculating Middle Return Value
Standard left <= right left = mid + 1 right = mid - 1 (left + right) / 2 mid / -1
Most Left Position left < right left = mid + 1 right = mid (left + right) / 2 left / -1
Most Right Position left < right left = mid right = mid - 1 (left + right) / 2 + 1 right / -1

Source:

  1. 二分查找、二分边界查找算法的模板代码总结
  2. Binary Search 二分法查找的三个模板