Vinn's Studio

Binary Search

Word count: 1.1kReading time: 6 min
2020/06/29 Share

Binary search can reduce the time complexity to O(logN) for sorted items' search. I summarized a framework to slove all the binary search problems under different situation in this post.

1. Framework

1.1. Main Factors

Here are some modifiable main factors for binary search problems.

  1. Right Boundary: The right boundary of the search range. len(nums) or len(nums)-1 are some commen choices.
  2. Continue Condition: The condition that binary search should continue. while(left <= right) or while(left < right) are some commen choices.
  3. Target Found: The action you take when found the target. Depends on specific problem.
  4. Search One/Other Part: If the target is not found, you wil then search the two divided parts. left = mid+1 and left = mid are 2 examples.

Where nums is the given list of numbers and target is the target number.

1.2. Main Framework

The main framework of binary search can be seen as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binarySearch(nums, target):
    left = 0
    right = 'Right Boundary'
    
    while 'Continue Condition':
        mid = (left + right) // 2
        
        if nums[mid] == target:
            'Target Found'
        elif nums[mid] < target:
            'Search One Part'
        elif nums[mid] > target:
            'Search The Other Part'
    return

Where nums is the given list of numbers and target is the target number.

2. Some Points

Based on different choices of right, our search interval can be different: If you let right = len(nums), then to search over nums, the index search interval should be [left, right); If you let right = len(nums)-1, then to search over nums, the index search interval should be [left, right]. In a word, based on how you set right, the search interval has two forms: [·,·) or [·,·]. Different forms have different settings, choose the suitable one based on specific problems.

2.1. Form One: Search [left, right)

  1. Right Boundary: right = len(nums)
  2. Continue Condition: while(left < right); the loop will stop when left == right, at which time the search interval is [right, right), which is an empty interval meaning that the loop should be stopped.
  3. Search One/Other Part: Each step we take a mid away, and then the search interval is divided into two parts: [left, mid) and [mid+1, right). To search the first part, we have right = mid; To search the latter part, we have left = mid+1.

2.2. Form Two: Search [left, right]

  1. Right Boundary: right = len(nums)-1
  2. Continue Condition: while(left <= right); the loop will stop when left == right+1, at which time the search interval is [right+1, right], which is an empty interval meaning that the loop should be stopped.
  3. Search One/Other Part: Each step we take a mid away, and then the search interval is divided into two parts: [left, mid-1] and [mid+1, right]. To search the first part, we have right = mid-1; To search the latter part, we have left = mid+1.

2.3. Notice

When the loop stops, all the items on the left of left will satisfies the if-else condition of left = mid+1；all the items on the right of right will satisfies the if-else condition of right = mid or right = mid-1.

3. Examples

3.1. Search a number

Given a list of numbers nums and a number target, try to find out if target is in nums or not. If so, return the index of target; otherwise, return -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binarySearch(nums, target):
    left = 0
    right = len(nums)-1 # Right Boundary
    
    while left <= right: # Continue Condition
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid # Target Found
        elif nums[mid] < target:
            left = mid + 1 # Search One Part
        elif nums[mid] > target:
            right = mid - 1 # Search The Other Part
    return -1

3.2. Koko Eating Bananas (LeetCode 875)

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

1
2
Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

1
2
Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

1
2
Input: piles = [30,11,23,4,20], h = 6
Output: 23

To find the minimum k, we can binary search k from 0 to max(piles), and check if it satisfies the condition (to finish eating all the bananas before the guards return):

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
47
48
49
50
51
52
53
### Form One: [left, right)
def minEatingSpeed(self, piles: List[int], h: int) -> int:  
    # Initalize the left and right boundaries     
    left = 1
    right = max(piles)

    while left < right:
        # Get the middle index between left and right boundary indexes.
        # hour_spent stands for the total hour Koko spends.
        middle = (left + right) // 2            
        hour_spent = 0

        # Iterate over the piles and calculate hour_spent.
        # We increase the hour_spent by ceil(pile / middle)
        for pile in piles:
            hour_spent += math.ceil(pile / middle)

        # Check if middle is a workable speed, and cut the search space by half.
        if hour_spent <= h:
            right = middle
        else:
            left = middle + 1

    # Once the left and right boundaries coincide, we find the target value,
    # that is, the minimum workable eating speed.
    return right

### Form Two: [left, right]
def minEatingSpeed(self, piles: List[int], h: int) -> int:  
    # Initalize the left and right boundaries     
    left = 1
    right = max(piles)

    while left <= right:
        # Get the middle index between left and right boundary indexes.
        # hour_spent stands for the total hour Koko spends.
        middle = (left + right) // 2            
        hour_spent = 0

        # Iterate over the piles and calculate hour_spent.
        # We increase the hour_spent by ceil(pile / middle)
        for pile in piles:
            hour_spent += math.ceil(pile / middle)

        # Check if middle is a workable speed, and cut the search space by half.
        if hour_spent <= h:
            right = middle - 1
        else:
            left = middle + 1

    # Once the left and right boundaries coincide, we find the target value,
    # that is, the minimum workable eating speed.
    return left

Author：Lingfeng Zhu

Original Link：https://lingfengzhu.github.io/2020/06/29/BinarySearch/

Published：June 29th 2020, 8:30:08 am

Updated：January 20th 2022, 3:17:49 pm

Copyright：This Article Uses Attribution-NonCommercial 4.0 International as the license

CATALOG
  1. 1. Framework
    1. 1.1. Main Factors
    2. 1.2. Main Framework
  2. 2. Some Points
    1. 2.1. Form One: Search [left, right)
    2. 2.2. Form Two: Search [left, right]
    3. 2.3. Notice
  3. 3. Examples
    1. 3.1. Search a number
    2. 3.2. Koko Eating Bananas (LeetCode 875)
Total : 33
2022
2021
2020
NLP Survival Analysis COVID-19 Conda Docker Python Hexo Web-Frontend Pytorch RecSys
Deep-Learning Algorithm Statistics Syntax Machine-Learning Finance