ChatGPT Gives a Correct Leetcode Solution (Rust: Binary Search Algorithm) after Several Attempts


I was trying to test the ChatGPT’s coding skills, thus I prompted it: “Solve the leetcode 704 using Rust”. This is a Binary Search Problem, see the following problem statement from leetcode:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:
1 <= nums.length <= 10^4
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.

rust-binary-search-runtime-error ChatGPT Gives a Correct Leetcode Solution (Rust: Binary Search Algorithm) after Several Attempts algorithms Artificial Intelligence Binary Search Algorithm ChatGPT (OpenAI) programming languages Rust

ChatGPT fails to give a correct Rust solution to solve the Leetcode 704 – Binary Search Algorithm

Binary Search Algorithm seems easy to understand, but there are some implementation details – which can be tricky e.g. how to handle the left and right boundaries. In coding interviews, it might be hard to get it right at the first attempt.

ChatGPT’s coding skills tested

Sure, here’s an example solution to LeetCode problem 704 “Binary Search” using Rust:

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len() - 1;
        
        while left <= right {
            let mid = left + (right - left) / 2;
            
            if nums[mid] == target {
                return mid as i32;
            } else if nums[mid] < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        -1
    }
}

Here, we define a method search on the Solution struct that takes a vector of integers nums and a target integer target, and returns the index of target in nums if it exists, or -1 if it does not.

The algorithm is a simple binary search: we keep track of the left and right indices of the search range, and repeatedly compute the midpoint of the range to determine which half to search next. If we find the target, we return its index; otherwise, we adjust the range and continue until the range is empty (i.e., left > right), at which point we know the target is not in nums.

I hope this helps!

Me: This solution gives runtime error “Line 9, Char 16: index out of bounds: the len is 1 but the index is 9223372036854775807 (solution.rs)”

I apologize for the error in my previous solution. The issue is that I assumed that right would always be a valid index in the nums vector, but this is not necessarily true when nums is empty.

Here’s an updated version of the solution that checks for the empty vector case and returns -1 immediately if it is empty:

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        if nums.is_empty() {
            return -1;
        }
        
        let mut left = 0;
        let mut right = nums.len() - 1;
        
        while left <= right {
            let mid = left + (right - left) / 2;
            
            if nums[mid] == target {
                return mid as i32;
            } else if nums[mid] < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        -1
    }
}

Now, if nums is empty, we immediately return -1. Otherwise, we proceed with the binary search algorithm as before.

I hope this updated solution works for you!

Me: still doesn’t work.

I apologize for the confusion. The issue with the previous solution was that the maximum value of right (9223372036854775807) was being computed when the input vector was empty, causing an index out of bounds error.

Here is another updated solution that should handle empty input vectors correctly:

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        if nums.is_empty() {
            return -1;
        }
        
        let mut left = 0;
        let mut right = nums.len() - 1;
        
        while left &tl;= right {
            let mid = left + (right - left) / 2;
            
            if nums[mid] == target {
                return mid as i32;
            } else if nums[mid] < target {
                left = mid + 1;
            } else {
                right = mid.checked_sub(1).unwrap_or(0);
            }
        }
        
        -1
    }
}

In this version, I use the checked_sub method instead of a simple subtraction to compute the new value of right when nums[mid] is greater than target. The checked_sub method returns None if the subtraction results in an underflow, which can happen when right is 0. In this case, I use the unwrap_or method to return either the result of checked_sub (i.e., right - 1) or 0, whichever is larger.

I hope this updated solution works for you. Please let me know if you have any further questions or issues.

Now, the solution has "Time Limit Exceeded" when the input is "nums=[5], target=-5"
I apologize for the previous solutions not meeting your needs. The issue with the previous solutions was that the algorithm still searched through the entire array even if the target value was not present in the array, which led to the "Time Limit Exceeded" error.

Here is another updated solution that should be more efficient and handle this case correctly:

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        if nums.is_empty() {
            return -1;
        }
        
        let mut left = 0;
        let mut right = nums.len() - 1;
        
        while left < right {
            let mid = left + (right - left) / 2;
            
            if nums[mid] < target {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if nums[left] == target {
            left as i32
        } else {
            -1
        }
    }
}

This solution is a slight variation on the standard binary search algorithm. Instead of continuing the search until the range is empty (left <= right), we stop when the range is reduced to a single element (left < right) and check whether that element is the target. This optimization ensures that the algorithm returns -1 immediately if the target is not present in the array.

I hope this solution works for you. Please let me know if you have any further questions or issues.

It takes several attempts

ChatGPT fails to give a correct solution at the begining - proving that it is AI - and not just copying and paste from some where else. However, when I fed it feedback, he/she has a good attitude (and apologizes when the code doesn't work). I started to feedback it error messages, and the ChatGPT finally presents a correct solution.

There are many ways to write a Binary Search Algorithm. Here is my solution based on the very first solution given by ChatGPT:

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left: i32 = 0;
        let mut right: i32 = nums.len() as i32 - 1;
        
        while left <= right {
            let mid = (left + (right - left) / 2);
            let v = nums[mid as usize];
            if v == target {
                return mid;
            } else if v < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        -1
    }
}

What is the Time and Space complexity of Binary Search?

The time complexity of this binary search algorithm is O(log n), where n is the length of the input vector nums. This is because the algorithm reduces the search range by half at each step, so it takes at most log n iterations to find the target or conclude that it is not present in the vector.

The space complexity of the algorithm is O(1), as it only uses a constant amount of extra space to store the left, right, and mid indices, regardless of the size of the input vector.

In summary, the time complexity of the algorithm is logarithmic with respect to the size of the input, and the space complexity is constant.

ChatGPT knows Recursion!

Me: Can you write it in Recursion?

Sure, here is the implementation of the binary search algorithm in Rust using recursion:

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        if nums.is_empty() {
            return -1;
        }
        
        let n = nums.len();
        let result = binary_search_recursive(&nums, 0, n - 1, target);
        result as i32
    }
}

fn binary_search_recursive(nums: &Vec<i32>, left: usize, right: usize, target: i32) -> i32 {
    if left > right {
        return -1;
    }
    
    let mid = left + (right - left) / 2;
    
    if nums[mid] == target {
        return mid as i32;
    } else if nums[mid] < target {
        return binary_search_recursive(nums, mid + 1, right, target);
    } else {
        return binary_search_recursive(nums, left, mid - 1, target);
    }
}

The binary_search_recursive function is a recursive implementation of the binary search algorithm. It takes the input vector nums, the left and right indices of the current search range, and the target value as arguments. The base case of the recursion is when left > right, which indicates that the search range is empty and the target value is not present in the vector. In this case, the function returns -1 to indicate failure. Otherwise, the function computes the middle index mid of the search range, compares the value at nums[mid] to the target value, and recursively searches the left or right half of the search range depending on whether the target value is less than or greater than the value at nums[mid].

The search function simply calls binary_search_recursive with the appropriate arguments and returns the result as an i32.

I hope this implementation helps! Let me know if you have any further questions.

Me: This solution gives a runtime error "Line 20, Char 8: index out of bounds: the len is 1 but the index is 9223372036854775807 (solution.rs)"

I apologize for the error in the previous implementation. The issue is that the function can recursively call itself with an empty search range, which can cause an index out of bounds error. Here is a modified implementation that avoids this issue:

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        binary_search_recursive(&nums, 0, n, target) as i32
    }
}

fn binary_search_recursive(nums: &[i32], left: usize, right: usize, target: i32) -> isize {
    if left >= right {
        return -1;
    }
    
    let mid = left + (right - left) / 2;
    
    if nums[mid] == target {
        return mid as isize;
    } else if nums[mid] < target {
        return binary_search_recursive(nums, mid + 1, right, target);
    } else {
        return binary_search_recursive(nums, left, mid, target);
    }
}

In this implementation, the binary_search_recursive function takes a slice of the input vector (&[i32]) instead of an owned vector (Vec<i32>), which avoids the need to pass the vector length as a separate argument. The function also uses >= instead of > for the base case of the recursion, which ensures that the function returns -1 when the search range is empty.

I hope this updated implementation works for you. Please let me know if you have any further questions or concerns.

What is the time and space complexity for this Recursion approach?

The time complexity of the binary search algorithm implemented with recursion is O(log n), where n is the length of the input vector nums. This is because the search range is divided in half at each recursive call, so the number of iterations required to find the target or conclude that it is not present is logarithmic with respect to the size of the input.

The space complexity of the recursion implementation is O(log n) as well, because the maximum depth of the recursion tree is log n. At each recursive call, the function allocates a new stack frame on the call stack to store the local variables and return address. Therefore, the total space used by the call stack is proportional to the depth of the recursion tree, which is logarithmic with respect to the size of the input.

In summary, the time complexity of the algorithm is logarithmic with respect to the size of the input, and the space complexity is also logarithmic due to the recursion.

Conclusion: Strong Coding Skills of ChatGPT

ChatGPT shows strong coding skills - however, it might give error code at the begining - just imagine ChatGPT is writing the code on the whiteboard - without compiler. As a human, we need to test the code for the ChatGPT. Imagine this is a coding interview - and I think ChatGPT is able to give a solution, explain it, and correct it (given feedbacks). ChatGPT is qualified for a mid-senior software engineer.

We have to admit that: it is not easy to write a good functioning Rust code in the first try. The Rust compilers are picky, on the types/conversion, on the ownership etc. Also, we have to prompt the ChatGPT in order to make it work for us effectively.

ChatGPT Use Cases

ChatGPT - AGI (Artificial General Intelligence)

ChatGPT Fails to

--EOF (The Ultimate Computing & Technology Blog) --

GD Star Rating
loading...
2536 words
Last Post: Teaching Kids Programming - Form Smallest Number From Two Digit Arrays (Set Intersection)
Next Post: Integrating ChatGPT Prompt AI to STEEM blockchain

The Permanent URL is: ChatGPT Gives a Correct Leetcode Solution (Rust: Binary Search Algorithm) after Several Attempts

Leave a Reply