二分查找

发表于： 分类于：
字数：595 阅读：≈ 2分钟 浏览：

二分查找

从一个从小到大的序列中找寻数goal, 采用二分查找。

思路：选择两个变量，分别赋值区间的首尾；选取区间的中间值与goal相比较，如果goal较大，那么将begin = middle, 如果goal较小, 那么 end = middle;考虑到begin和end可能相等，goal会在边界被找到，那么循环条件为begin <= end

func binarySearch(arr []int, goal int) (index int) {
	begin := 0
	end := len(arr)-1
	for ;begin <= end; {
		middle := (end + begin) / 2
		if arr[middle] < goal {
			begin = middle
		} else if arr[middle] > goal {
			end = middle
		} else {
			return middle
		}
	}
	return -1
}

上述思路未考虑到边界条件中这种情况。例如区间为[5, 6],goal>arr[5]的情况，此时区间此后将一直是[5,6]不会向前移动。（此种情况不会出现左边界，即goal == arr[5])

思路：当arr[middle] < goal时，begin = middle+1；当arr[middle] > goal时， end = middle or end = middle - 1。加1或减1不会使过程中出现界限被超出

func binarySearch(arr []int, goal int) (index int) {
	begin := 0
	end := len(arr)-1
	for ;begin <= end; {				//"=" 展示可能出现边界情况
		middle := (end + begin) / 2
		if arr[middle] < goal {
			begin = middle+1
		} else if arr[middle] > goal {
			end = middle-1
		} else {
			return middle
		}
	}
	return -1
}

二分查找中个人认为区间应该始终为左闭右闭区间。不应该使循环代码中begin,end变量来维持区间的开闭性质

func search( nums []int ,  target int ) int {
	// write code here
	low, high := 0, len(nums)-1
	for ; low <= high; {
		mid := low + (high-low) / 2
		fmt.Println(low, high, mid)
		if nums[mid] < target {
			low = mid+1
		} else if nums[mid] > target {
			high = mid-1
		} else {
			j := mid-1
			for ; j >= 0; j-- {
				if (nums[j] != target) {
					break
				}
			}
			return j+1
		}
	}
	return -1
}

测试用例[1, 2, 2, 3, 4],2 输出结果应为1

resource