package main

import (
    "fmt"
)

func main() {
    arr := []int{1, 3, 3, 5, 7, 9, 11, 13}
    n := len(arr)

    index := bsearch(arr, n, 9)

    fmt.Println(index)

}

//正常情況
func bsearch(a []int, n, val int) int {
    low := 0
    high := n - 1
    for low <= high {
        // mid := (low + high) / 2
        // mid := low + (high-low)/2
        mid := low + ((high - low) >> 1)
        if a[mid] == val {
            //無重復數(shù)據(jù)
            return mid
            //返回第一個值等于給定值的元素
            // if mid == 0 || a[mid-1] != val {
            //  return mid
            // } else {
            //  high = mid - 1
            // }
            //返回最后一個值等于給定值的元素
            // if mid == n-1 || a[mid+1] != val {
            //  return mid
            // } else {
            //  low = mid + 1
            // }

        } else if a[mid] > val {
            high = mid - 1
        } else if a[mid] < val {
            low = mid + 1
        }
    }
    return -1 //不存在
}

//第一個大于給定值
// func bsearch(a []int, n, val int) int {
//  low := 0
//  high := n - 1
//  for low <= high {
//      mid := low + ((high - low) >> 1)
//      if a[mid] > val {
//          if mid == 0 || a[mid-1] <= val {
//              return mid
//          } else {
//              high = mid - 1
//          }
//      } else {
//          low = mid + 1
//      }
//  }
//  return -1
// }

//最后一個小于給定值
// func bsearch(a []int, n, val int) int {
//  low := 0
//  high := n - 1
//  for low <= high {
//      mid := low + ((high - low) >> 1)
//      if a[mid] < val {
//          if mid == n || a[mid+1] >= val {
//              return mid
//          } else {
//              low = mid + 1
//          }
//      } else {
//          high = mid - 1
//      }
//  }
//  return -1
// }