查找算法

二分查找

前提是数组有序，二分查找时间复杂度O(logN)

func BinarySearch(data []int, target int) int {
	var low, high, mid int
	low, high = 0, len(data) - 1

	for low <= high {
		mid = low + (high-low)/2    //防止溢出

		if data[mid] > target {
			high = mid - 1
		} else if data[mid] < target {
			low = mid + 1
		} else {
			return mid
		}
	}

	return -1
}

如果有序数组里面有重复数字，要查找重复数字的左右边界，可基于上述二分查找算法略加修改即可。
如查找左边界：return mid 处改为 high=mid-1，return -1 处改为 return low。另外需要加一段判断left越界情况的逻辑 if left > len(data)-1 || data[left] != target 则return -1

TopK问题

quick select 快速选择算法

quick select 算法的主要目的是在一个没有排序的数组里面，找到第k小的元素。
快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度，从O(n log n)至O(n)，不过最坏情况仍然是O(n2)。

func quickselect(nums []int, start, end, k int) int {
	// use last element as pivot
	pivotIndex := partition(nums, start, end, end)

	if k-1 == pivotIndex {
		return nums[pivotIndex]
	} else if k-1 > pivotIndex {
		return quickselect(nums, pivotIndex+1, end, k)
	} else {
		return quickselect(nums, start, pivotIndex-1, k)
	}
}

func partition(nums []int, start, end, pivot int) int {
	// move pivot to end
	nums[end], nums[pivot] = nums[pivot], nums[end]
	pivotValue := nums[end]
	i := start
	for j := start; j < end; j++ {
		if nums[j] > pivotValue {
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
	}
	// move pivot to its sorted position
	nums[i], nums[end] = nums[end], nums[i]
	// return pivot index
	return i
}