leetcode month day 3: binary search

Should have been an easy one, but I haven’t written one by hand in years. Ended up Googling.

Some interesting notes on the code:

• for with a conditional break inside is considerably slower than for condition.
• The version of this that I learned back when used a step division, and that actually is much harder to get right. The upper/lower/mid version is much easier to get right.
• I decided to not do a recursive solution this time on purpose. The expressivity that recursion gives you is not to be denied.

Final version scored well: 90% on speed, 97% on memory. Acceptable, but the amount of dicking around was not. Note: study up more of these common but not commonly coded algorithms.

func search(nums []int, target int) int {
    // Find midpoint, check element; equal, less, or greater.
    // if the step size goes to 0 we did not find.
    low := 0
    high := len(nums) -1

    for low <= high {
        mid := (high + low )/ 2
        if nums[mid] < target {
            low = mid + 1
        } else if nums[mid] > target {
            high = mid -1
        } else {
            return mid
        }
    }
    return -1
}