Golang binary search solution


  • 1

    The important point is we can take nums[-1] and nums[len(nums)] as -∞.
    Let's say we take a middle element and it looks like

               ↓ mid
    ..., 100, 200, 150, ...
    

    Now we can find the peak, so we can return mid. If this is not the case, either the left or right element of mid is bigger than nums[mid]. For example,

               ↓ mid
    ..., 500, 200, 150, ...
    

    500 is bigger than 200. In this case, because left starts from -∞, there is at least one peak on the left side of mid.
    Same applies on the right side.

    func findPeakElement(nums []int) int {
    	nlen := len(nums)
    	if nlen == 1 {
    		return 0
    	}
    
    	left, right := 0, nlen-1
    	for {
    		mid := left + (right-left)/2
    
    		// edge case first element
    		if mid == 0 {
    			if nums[mid] > nums[mid+1] {
    				return mid
    			}
    			left = mid + 1
    			continue
    		}
    		// edge case last element
    		if mid == nlen-1 {
    			if nums[mid] > nums[mid-1] {
    				return mid
    			}
    			right = mid - 1
    			continue
    		}
    
    		if nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1] {
    			return mid
    		}
    		if nums[mid] < nums[mid-1] {
    			right = mid - 1
    		} else {
    			left = mid + 1
    		}
    	}
    	return -1 // never reaches here
    }
    

Log in to reply
 

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