If num[-1]=num[n]=+∞, can we still use binary search?


  • 0
    G

    I think the reason that the binary search works is that outside the range specified by start and end, left is a small element and right is also a small element. It keeps dividing the list into smaller list with the property until the length of the list is 1.

    A sample binary search solution is below.

    int findPeakElement2(int[] n)
    {
    	int start = 0, end = n.length - 1;
    	while (start <= end)
    	{
    		int c = (end + start) / 2;
    		if (c + 1 < n.length && n[c] < n[c + 1])
    			start = c + 1;
    		else if (c - 1 >= 0 && n[c] < n[c - 1])
    			end = c - 1;
    		else
    			return c;
    	}
    	return start;
    }
    

    Therefore I wonder if num[-1]=num[n]=+∞, which breaks the mentioned property, can we still use binary search? Is there still O(log n) solution?


  • 0
    C

    I don't think so.
    For example, array only contains one element, say A[1] = {2};
    Since num[-1]=num[n]=+∞, there's even no peak value in this case.


Log in to reply
 

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