Confusion on binary search and please help me


  • 1
    W

    I have been struggling on binary search for a long time. I read many materials trying to figure out a "correct" way to write binary search code in different situations. Unfortunately, I still can not write it correctly at a very short time. My things is like this, for example, this problem, the most voted post is like :

    int findMin(vector<int> &num) {
    int lo = 0;
    int hi = num.size() - 1;
    int mid = 0;

        while(lo < hi) {
            mid = lo + (hi - lo) / 2;
            
            if (num[mid] > num[hi]) {
                lo = mid + 1;
            }
            else if (num[mid] < num[hi]) {
                hi = mid;
            }
            else { // when num[mid] and num[hi] are same
                hi--;
            }
        }
        return num[lo];
    }
    

    My confusions are, how to set the loop test condition low < hi or lo <= hi and how to shrink the search space, by mid + 1 or by mid. I see some people using combinations of these two. But every time I write my own code, either I miss the answer in shrinking (maybe should use lo = mid instead of lo = mid + 1) or I got TLE since the loop wont terminate(may be should let lo = mid + 1 instead of lo = mid, since mid + 1 decreased the search space by at least one, which will finally terminates the loop).

    Any help would be appriciated!


Log in to reply
 

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