/*
 * @Description: 二分查找
 * @Version: 2.0
 * @Autor: zhuyijun
 * @Date: 2021-03-29 09:08:50
 * @LastEditors: zhuyijun
 * @LastEditTime: 2021-03-30 08:59:23
 */
package main

import "fmt"

/**
二分查找算法
*/
func BinarySearch(key int, a []int) int {
	start := 0
	end := len(a) - 1
	for start < end {
		mid := start + ((end - start) >> 1)
		if key < a[mid] {
			end = mid - 1
		} else if key > a[mid] {
			start = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

//查找第一个值等于给定值得元素
func BinarySearch2(nums []int, value int) int {
	length := len(nums)
	start := 0
	end := length - 1
	for start <= end {
		mid := start + ((end - start) >> 1)
		if nums[mid] > value {
			end = mid - 1
		} else if nums[mid] < value {
			start = mid + 1
		} else {
			for mid >= 0 {
				if nums[mid-1] == value {
					mid--
				} else {
					return mid
				}
			}
		}
	}
	return -1
}

// 查找最后一个值等于给定值的元素
func BinarySearch3(nums []int, value int) int {
	start := 0
	end := len(nums) - 1
	for start <= end {
		mid := start + ((end - start) >> 1)
		if nums[mid] > value {
			end = mid - 1
		} else if nums[mid] < value {
			start = mid + 1
		} else {
			for mid < len(nums) {
				if nums[mid+1] == value {
					mid++
				} else {
					return mid
				}
			}
		}
	}
	return -1
}

// 查找第一个大于等于给定值的元素
func BinarySearch4(nums []int, value int) int {
	start := 0
	end := len(nums) - 1
	for start <= end {
		mid := (start + end) >> 1
		if nums[mid] < value {
			start = mid + 1
		} else {
			for mid >= 0 {
				if nums[mid-1] >= value {
					mid--
				} else {
					return mid
				}
			}
		}
	}
	return -1
}

// 查找最后一个小于等于给定值的元素
func BinarySearch5(nums []int, value int) int {
	start := 0
	end := len(nums) - 1
	for start <= end {
		mid := (start + end) >> 1
		if nums[mid] > value {
			end = mid - 1
		} else {
			for mid < len(nums) {
				if nums[mid+1] <= value {
					mid++
				} else {
					return mid
				}
			}
		}
	}
	return -1
}

func main() {
	var a = []int{0, 2, 4, 7, 9, 11, 45, 67, 99, 100}
	var i int = 2
	key := BinarySearch(i, a)
	if key > 0 {
		fmt.Printf("已查到:%d,位置在:%d \n", i, key+1)
	} else {
		fmt.Printf("没有查到a数组中有%d", i)
	}
}