Is there a standard way of implementing a bug-free binary search ?


  • 0
    P

    I have following concerns when solving this problem using binary search:
    (1) what is the condition of ending the while loop, i.e., start + 1 < end or start < end (2) how to update bounds, i.e., start = mid or start = mid + 1 (3) which bound is the final result.

    My way of avoiding pitfall is using start + 1 < end as the condition where the while loop ends. Then I can update both bounds with start = mid or end = mid. To guarantee my result is correct, I do a final check. Any suggestion? Thank you in advance!

     int findDuplicate(vector<int>& nums) {
                int start = 0;
                int end = nums.size() - 1;
                while (start + 1 < end) {
                    int mid = start + (end - start) / 2;
                    int cnt = 0;
                    for (auto num : nums) {
                        if (num <= mid) cnt++;
                    }
                    
                    if (cnt > mid) 
                        end = mid;
                    else
                        start = mid;
                }
                
                int cnt = 0;
                for (auto num : nums) {
                    if (num == start) {
                        cnt++;
                        if (cnt > 1) 
                            return start;
                    }
                }
                return end;
            }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.