如何使用分治算法的思想，分治的技巧详解

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right + left) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		}
	}

	return -1
}

/**
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return 	 	      true if current version is bad
 *			          false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
	left, right := 0, n
	for left < right {
		mid := (right + left) / 2
		if isBadVersion(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return right
}

// 测试函数
func isBadVersion(n int) bool {
	return false
}

func QuickSort(arr []int) {
	quickSort(arr, 0, len(arr)-1)
}

func quickSort(data []int, l, u int) {
	if l < u {
		m := partition(data, l, u)
		quickSort(data, l, m-1)
		quickSort(data, m, u)
	}
}

func partition(data []int, l, u int) int {
	quick := data[l]
	left := l

	for i := l + 1; i <= u; i++ {
		if data[i] <= quick {
			left++
			data[left], data[i] = data[i], data[left]
		}
	}
	data[l], data[left] = data[left], data[l]
	return left + 1
}

func MergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	mid := len(arr) / 2
	leftArr := MergeSort(arr[0:mid])
	rightArr := MergeSort(arr[mid:])
	return merge(leftArr, rightArr)
}

func merge(left, right []int) []int {
	i, j := 0, 0
	m, n := len(left), len(right)
	var result []int
	// 合并子序列
	for {
		// 任何一个区间遍历完成就退出
		if i >= m || j >= n {
			break
		}
		if left[i] > right[j] {
			result = append(result, right[j])
			j++
		} else {
			result = append(result, left[i])
			i++
		}
	}

	// 左边的子集没有遍历完成，将左侧的放入到结果集
	if i < m {
		result = append(result, left[i:]...)
	}

	// 右侧的子集没有遍历完成，将右侧的放入到结果集中
	if j < n {
		result = append(result, right[j:]...)
	}

	return result
}

func MergeSort(nums []int) []int {
	mergeSort(nums, 0, len(nums)-1)
	return nums
}

func mergeSort(nums []int, start, end int) {
	if start >= end {
		return
	}
	mid := start + (end-start)/2
	mergeSort(nums, start, mid)
	mergeSort(nums, mid+1, end)
	var tmp []int
	i, j := start, mid+1
	for i <= mid && j <= end {
		if nums[i] > nums[j] {
			tmp = append(tmp, nums[j])
			j++
		} else {
			tmp = append(tmp, nums[i])
			i++
		}
	}
	if i <= mid {
		tmp = append(tmp, nums[i:mid+1]...)
	}
	if j <= end {
		tmp = append(tmp, nums[j:end+1]...)
	}
	for i := start; i <= end; i++ {
		nums[i] = tmp[i-start]
	}
}

func reversePairs(nums []int) int {
	return mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, start, end int) int {
	if start >= end {
		return 0
	}
	mid := start + (end-start)/2
	cnt := mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end)
	tmp := []int{}
	i, j := start, mid+1
	for i <= mid && j <= end {
		if nums[i] > nums[j] {
			tmp = append(tmp, nums[j])
			cnt += mid - i + 1
			j++
		} else {
			tmp = append(tmp, nums[i])
			i++
		}
	}
    
    if i <= mid {
        tmp = append(tmp, nums[i:mid+1]...)
    }
    if j <= end{
        tmp = append(tmp, nums[j:end+1]...)
    }
	for i := start; i <= end; i++ {
		nums[i] = tmp[i-start]
	}
	return cnt
}

var count int = 0

func main() {
	beadNum := 5 // This is the initial number of beads
	hanoi(beadNum, "A", "B", "C")
	fmt.Println(count)
}

func hanoi(beadNum int, pillarA string, pillarB string, pillarC string) {
	if beadNum == 1 {
		// 最后一个了，可以结束了
		move(beadNum, pillarA, pillarC)
	} else {
		// Step 2: 将 N-1 层从 A 移动到 B
		hanoi(beadNum-1, pillarA, pillarC, pillarB)
		// Step 2: 将第 N 层从 A 移动到 C
		move(beadNum, pillarA, pillarC)
		// Step 3: 将 B 中的 N-1 层移动到 C
		hanoi(beadNum-1, pillarB, pillarA, pillarC)
	}
}

func move(beadNum int, pillarFrom string, pillarTo string) {
	count += 1
}