About Binary Search

當我剛開始寫Binary Search的題目時，最常遇到的幾個bug是

• While Loop不會停
• IndexOutOfBound
• While Loop停了，但我搞不清楚得到的indexe代表的是什麼，需要+1 or -1嗎?

後來參考了一些Leetcode上的解法，整理出了一個pattern，可以很簡單的避免上面的幾個常見的問題，在這邊分享給大家。

Mental Model

比起叫它Binary Search，我比較喜歡把我的方法叫做Binary Partition，因為這個pattern的核心精神並不是在search, 而是把input切成兩段，然後在兩段的交界點拿出我們所需要的那個值。

至於怎麼切段呢，簡單說就是符合條件放左邊，不符合的放右邊，要注意我們是切段而不是分段，意思就是我們不會去改變原本input的order, 所以可以使用的條件是有限制的，像是odd/even就不適用，因為那樣並不是永遠能切段，例如[1, 2, 3, 4, 5]。在剩下的文章中，我們會把切段的條件叫做Arbitator

type Arbitator interface {
  Qualify(v interface{}) bool
}

讀到這，你可能會想問說，我們不是在聊binary search嗎? 怎麼忽然變成怎麼切array了呢? 這就是這篇文章的重點了，利用Arbitator的實作，我們可以利用Binary Partition來做Binary Search。在這邊，我們先用一個經典的題目來當例子 - Find the index of a value from a sorted array，要找到target value，我們可以把input array切成包含target value的一段，跟不包含target value的一段，然後因為順序並不能/不會改變，包含target value的那段的最左或最右的值就是我們所要的。

用個實際的例子，在1, 3, 7, 12, 50, 77, 98找出77的index, 我們可以把Arbitator定義成

func (a *LessThan77) Qualify(v int64) bool {
  return v < 77
}

然後我們會得到
arr[:5] -> [1, 3, 7, 12, 50] - 這段不考慮，因為他們都比77小
arr[5:] -> [77, 98] - 我們只需要check這段的第一個值是不是77，因為這段的值都是等於或是大於77的，如果第一值不是77，後面的值也不可能是，因為他們會愈來愈大

Binary Partition

在這邊，我們先看一下Partition的實作

func BinaryPartition(arr []interface{}, arbitator Arbitator) (int, int) {
  l, r := 0, len(arr)-1
  
  for ;l <= r; {
    m := (l+r)>>1
    if arbitator.Qualify(arr[m]) {
      l = m+1
    } else {
      r = m-1
    }
  }
  
  // r is the inclusive right end of the qualified section.
  // l is the inclusive left end of the non qualified section.
  return r, l
}

最後三行的comment很明白的寫出整個while loop在做的事, 把r跟l移到他們該去的位置。簡單的來說，當loop停止的時候，array是這樣的

qualified, ..., R (qualified), L (unqualified), ..., unqualified

跟Binary Search很像的，我們每次去掉array的一半，BinaryPartition的time complexity是O(logN)。

A complete example

To find a target number in a sorted array

Go playground link

package main

import "fmt"

type Arbitator interface {
	Qualify(v int) bool
}

func BinaryPartition(arr []int, arbitator Arbitator) (int, int) {
	l, r := 0, len(arr)-1

	for l <= r {
		m := (l + r) >> 1
		if arbitator.Qualify(arr[m]) {
			l = m + 1
		} else {
			r = m - 1
		}
	}

	// r is the inclusive right end of the qualified section.
	// l is the inclusive left end of the non qualified section.
	return r, l
}

type SmallerThan struct{ Target int }

func (s *SmallerThan) Qualify(v int) bool {
	return v < s.Target
}

func binarySearch(arr []int, target int) int {
	smallerThan := &SmallerThan{target}

	_, largeOrEuqal := BinaryPartition(arr, smallerThan)
	if arr[largeOrEuqal] == target {
		return largeOrEuqal
	}
	return -1
}

func main() {
	arr := []int{1, 5, 7, 9, 20, 40, 100, 140, 200}
	fmt.Println(binarySearch(arr, 40))
	fmt.Println(binarySearch(arr, 99))
	fmt.Println(binarySearch(arr, 1))
}

For complex problems

我們接下來還會看怎麼用這個pattern來處理一些有趣的問題，不過先寫到這，很快會回來補完。