题解 | 在数组中找到一个局部最小的位置

package main

import (
    "fmt"
)

func main() {
    num := 0
    for {
        n, _ := fmt.Scan(&num)
        if n == 0 {
            break
        } else {
            arr := make([]int, num)
            for i:=0; i<len(arr); i++ {
                fmt.Scan(&arr[i])
            }
            fmt.Println(process(arr, 0, len(arr)-1))
        }
    }
}

// 利用二分查找原型，找中间点，看能不能找到满足条件的
// 找不到去左边找，左边找不到去右边找，最差情况下也得o(n)
func process(arr []int, l, r int) int {
	if l >= r {
		return -1
	}
	mid := (r-l)/2 + l

	if mid-1 >= 0 && mid+1 <= len(arr)-1 && arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1] {
		return mid
	} else if mid-1 < 0 && mid+1 <= len(arr)-1 && arr[mid] < arr[mid+1] {
		return mid
	} else if mid-1 >= 0 && mid+1 > len(arr)-1 && arr[mid] < arr[mid-1] {
		return mid
	} else {
		left := process(arr, l, mid-1)
		if left != -1 {
			return left
		}
		right := process(arr, mid+1, r)
		if right != -1 {
			return right
		}
		return -1
	}
}