// File: binary_search.go
// Created Time: 2022-12-05
// Author: Slone123c (274325721@qq.com)

package chapter_searching

/* Бинарный поиск (двусторонне замкнутый интервал) */
func binarySearch(nums []int, target int) int {
	// Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
	i, j := 0, len(nums)-1
	// Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
	for i <= j {
		m := i + (j-i)/2      // Вычислить индекс середины m
		if nums[m] < target { // Это означает, что target находится в интервале [m+1, j]
			i = m + 1
		} else if nums[m] > target { // Это означает, что target находится в интервале [i, m-1]
			j = m - 1
		} else { // Целевой элемент найден, вернуть его индекс
			return m
		}
	}
	// Целевой элемент не найден, вернуть -1
	return -1
}

/* Бинарный поиск (лево замкнутый, право открытый интервал) */
func binarySearchLCRO(nums []int, target int) int {
	// Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
	i, j := 0, len(nums)
	// Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
	for i < j {
		m := i + (j-i)/2      // Вычислить индекс середины m
		if nums[m] < target { // Это означает, что target находится в интервале [m+1, j)
			i = m + 1
		} else if nums[m] > target { // Это означает, что target находится в интервале [i, m)
			j = m
		} else { // Целевой элемент найден, вернуть его индекс
			return m
		}
	}
	// Целевой элемент не найден, вернуть -1
	return -1
}