Leetcode: Binary Search

Leetcode #704 : Binary Search

• Perform a binary search to directly find the solution in O(logn).

• Have two pointers, l and r, where l = left pointer and r= right pointer.

• Calculate point between your left and right pointers. int middle = (l + r) / 2;

• If the middle index is the val, simply return, if not, adjust l or `
  

---

title: ‘Leetcode 704: Binary Search ’ pubDate: 2024-04-19 description: ‘Leetcode 704: Binary Search’ author: ‘Christian’ image: url: ‘https://docs.astro.build/assets/full-logo-light.png’ alt: ‘The full Astro logo.’ tags: [“Computer Science”, “blogging”, “What’s next”]

Published on: 05/07/2024

---

Solution

The idea is simple…

public int search(int[] nums, int target){
    int l = 0;
    int r = vals.length - 1;
    int m = 0;
    while(l <= r){
        m = (l + r) / 2;
        int curr = vals[m];
        
        // Target is found.
        if(curr == target){
            return m;
        }
        else if(curr > target){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }
    // Return -1 if the target isn't found.
    return -1;
}

---

It is not difficult to see that this could be solved using a classic algorithm - Binary Search. Let us see how the search space could be halved each time below

- Scenario #1: isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B       G = Good, B = Bad
 |       |       |
left    mid    right

Let us look at the first scenario above where isBadVersion(mid) => false. We know that all version preceding and including mid are all good. So we set left = mid + 1 to indicate that the new search space is the interval [mid + 1, right] (inclusive).

+ Scenario #2: isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B       G = Good, B = Bad
 |       |       |
left    mid    right

The only scenario left is where isBadVersion(mid) => true. This tells us that mid may or may not be the first bad version, but we can tell for sure that all versions after mid can be discarded. Therefore we set right == mid as the new search space of interval [left, mid] (inclusive).

In our case, we indicate left and right as the boundary of our search space (both inclusive). This is why we initiate left = 1 and right = n. How about the terminating condition? We could guess that left and right eventually both meet and it must bt the first bas version, but how could you tell for sure?

The formal way is to prove by induction.

If you are setting mid = (left + right) / 2, you have to be very careful. Unless you are using a language that does not overflow such as Python, left + right could overflow. One way to fix this is to use

left + (right - left) / 2 instead.

If you fall into this subtle overflow bug, you are not alone. Even Jon Bentley’s own implementation of binary search had this overflow bug and remained undetected for twenty years.

Solution

public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

---

---

public int search(int[] nums, int target){
    int l = 0;
    int r = vals.length - 1;
    int m = 0;
    while(l <= r){
        m = (l + r) / 2;
        int curr = vals[m];
        
        // Target is found.
        if(curr == target){
            return m;
        }
        else if(curr > target){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }
    // Return -1 if the target isn't found.
    return -1;
}

Leetcode #278 : First Bad Version

- Scenario #1: isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B       G = Good, B = Bad
 |       |       |
left    mid    right

+ Scenario #2: isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B       G = Good, B = Bad
 |       |       |
left    mid    right

public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

The end! :)