interview-arithmetic/leetcode/剑指offer/在排序数组中查找数字 I/main_optimize.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	input := bufio.NewScanner(os.Stdin)
	var output int
	var digits []int
	var target int
	for input.Scan() {
		line := input.Text()

		digits = []int{}
		values := strings.Split(line, " ")
		length := len(values)

		for index, v := range values {
			d, _ := strconv.Atoi(v)
			if index == length-1 {
				target = d
				break
			}
			digits = append(digits, d)
		}

		fmt.Println("start ---", digits, target)
		output = search(digits, target)
		fmt.Println(output)
	}
}
func search(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}
	var leftIdx = binarySearchLeft(nums, target)
	var rightIdx = binarySearchLeft(nums, target+1)

	if nums[leftIdx] != target {
		return 0
	}
	if leftIdx == rightIdx {
		return 1
	}
	if nums[rightIdx] == target {
		rightIdx += 1
	}
	return rightIdx - leftIdx
}

// left最后都会和right相等，nums[right]永远大于等于target。
// 就会使得nums[left]永远小于等于target.for结束的时候left和right相等，
// 所以只需要判断nums[left] ?= target, 就能判断nums中是否存在target
func binarySearchLeft(nums []int, target int) int {
	var left, right = 0, len(nums) - 1
	var mid int
	for left < right {
		mid = (left + right) / 2
		if nums[mid] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}