二分探索の実装

半閉区画

最初に見つけたtargetのインデックスを返す場合

半閉区画の場合、rightは常に探索済みの範囲に含める必要がある。そのため範囲外のインデックス（len(nums)）で初期化する必要があるし、すでに探索済みの値（mid）で更新する必要がある。またleft == rightになるということはleftも探索済みとなり、全ての探索が終了したことがわかるので、探索を終了する必要がある。

// 半閉区画（最初に見つけたtargetのインデックスを返す）
// nums := []int{0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; target := 1;のとき、インデックス5が返される
func search(nums []int, target int) int {
  left, right := 0, len(nums)
  for left < right {
    mid := left + (right-left)/2
    if nums[mid] == target {
      return mid
    }
    if target < nums[mid] {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return -1
}

target未満の値の場合はfalse、target以上の値の場合はtrueだとすると、探索対象の数列は[false, false, ..., true, true, ...]のようなbool値の集合と捉えることができる。falseとtrueの境界にいる場合はleftはmid + 1でfalseからtrueに更新される。一方で、rightはmidがtrueの場合にmidで更新されるので、常にtrueの範囲内に居続ける（インデックスの範囲外もtrueとみなすなら）し、いきなりrightがleftを飛び越える（right < left）ことはない。そのため、下記のように書くこともできる。

// 半閉区画（最初に見つけたtargetのインデックスを返す）
// nums := []int{0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; target := 1;のとき、インデックス5が返される
func search(nums []int, target int) int {
  left, right := 0, len(nums)
  for {
    if left == right {
      break
    }
    mid := left + (right-left)/2
    if nums[mid] == target {
      return mid
    }
    if target < nums[mid] {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return -1
}

境界の右側を返す場合

ところで同じ二分探索でも、同じtargetならどのtargetでも良いのか、それとも最初のtarget（falseとtrueの境界）を返したいのかで実装が変わってくる。これまでに提示した２つの例はどちらも同じtargetならどのtargetでも返して良いという考えのもとつくられた実装である。この場合、例えばnums := []int{0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; target := 1;のとき、インデックス5が返される。一方で最初の1（インデックス2）を返して欲しい場合はこれまでの実装では適さない。

最初の1（インデックス2）を返す実装を作りたい場合は、最初のtrue（falseとtrueの境界）を求めてから、そのtrueがtargetかどうかを確かめるという方法を取れば良い。

rightがleftを飛び越えることはないので、必ずleft == rightになった瞬間がfalseとtrueの境界だとわかる。leftがfalseからtrueの境界に入ったときに、rightがleft < rightの位置にいる可能性はあるが、その場合は必ずtarget < nums[mid]になるので、leftは動かず、rightのみが更新されて徐々にleftに近づいていき、最終的にleftとrightは重なる。

left == rightになったとき、leftとrightはともに一番最初にあるtrueにいるが、全てfalseの場合はrightは範囲外のインデックスのまま動かないし、trueが存在するとしてもtarget自体は存在しない可能性が考えられるので、このときのleftまたはrightの値がtargetと一致するかを確認する必要がある。

// 半閉区画（境界の右側を返す）
// nums := []int{0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; target := 1;のとき、インデックス2が返される
func search(nums []int, target int) int {
  left, right := 0, len(nums)
  for left < right {
    mid := left + (right-left)/2
    if nums[mid] < target {
      left = mid + 1
    } else {
      right = mid
    }
  }
  if left >= len(nums) || nums[left] != target {
    return -1
  }
  return left
}

// 半閉区画（境界の右側を返す）
// nums := []int{0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; target := 1;のとき、インデックス2が返される
func search(nums []int, target int) int {
  left, right := 0, len(nums)
  for left < right {
    mid := left + (right-left)/2
    if nums[mid] < target {
      left = mid + 1
    } else {
      right = mid
    }
  }
  if right >= len(nums) || nums[right] != target {
    return -1
  }
  return right
}

閉区画

最初に見つけたtargetのインデックスを返す場合

対して閉区画の場合は、rightは常に未探索の範囲に含める必要があるため、len(nums)-1で初期化し、mid + 1で更新する必要がある。またrightもfalseとtrueの境界にいる場合はmid - 1でtrueからfalseに更新されるため、leftとrightはtrueの範囲内（最初のtrue）で重なる場合もあれば、falseの範囲内（最後のfalse）で重なる可能性もある。trueの範囲内で重なる場合は、必ずtarget < nums[mid]となるので、leftは動かず、rightだけが更新されてfalseの範囲内に入ることになる。反対にfalseの範囲内で重なる場合は、rightは動かず、leftがtrueの範囲内に入ることになる。そのため、left == rightの時はまだ探索を続ける必要があり、right < leftとなったときに初めて探索を終了することができる。

これは考えてみれば当たり前で、閉区画の場合rightは未探索の範囲に含まれているので、left == rightの時はまだ未探索の領域が残っているため、探索を続ける必要があると捉えることができ、right < leftとなったときに初めて未探索の領域がなくなるので探索を終了することができるわけである。

ちなみに下記の実装ではnums := []int{0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; target := 1;のとき、インデックス4が返される。半閉区画と違ってrightがlen(nums)-1で初期化されているためである。この実装はtargetならなんでも良いので返すという実装なので、どのインデックスを返そうがあまり大きな違いはない。

// 閉区画（最初に見つけたtargetのインデックスを返す）
// nums := []int{0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; target := 1;のとき、インデックス4が返される
func search(nums []int, target int) int {
  left, right := 0, len(nums)-1
  for left <= right {
    mid := left + (right-left)/2
    if nums[mid] == target {
      return mid
    }
    if target < nums[mid] {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return -1
}

境界の右側を返す場合

right < leftとなった瞬間、rightはfalseの範囲内に入ってしまっているが、leftは必ず一番最初にあるtrueにいる。そのため、下記のようにも書くことができる。一方で、閉区画のようにrightを返すことはできない。

// 閉区画（境界の右側を返す）
// nums := []int{0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; target := 1;のとき、インデックス2が返される
func search(nums []int, target int) int {
  left, right := 0, len(nums)-1
  for left <= right {
    mid := left + (right-left)/2
    if nums[mid] < target {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  if left >= len(nums) || nums[left] != target {
    return -1
  }
  return left
}