704. 二分查找 #

题目地址 #

解题思路 #

可以参考

对于常规实现来说，在解题时要区分区间，也就是左闭右闭还是左闭右开区间两种解法，其实就是要区分右闭还是右开，在临界条件判断时包不包含最右边的值。

对于左闭右闭来说，包含最右边，所以在临界条件判断时，左边的值可以等于右边的值，那么right其实是数组长度-1，也就是数组最后一个值。

while (left <= right)，因为left == right是有意义的，所以使用<=
if (nums[middle] > target)，right要赋值为middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是middle - 1

但是对于左闭右开来说，因为不包含最右元素，那么right其实就是数组长度，right 取不到数组最后一个值。

while (left < right)，因为left == right在区间[left, right)是没有意义的，所以这里要用<
if (nums[middle] > target) right更新为middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，也就是说，下一个查询区间不会去比较nums[middle]

具体实现 #

区间左闭右闭

package main

import (
	"fmt"
)

func main() {
	arr := []int{0, 1, 2, 3, 4, 5, 10}
	fmt.Println(binarySearch(arr, 10))
}

func binarySearch(nums []int, target int) int {
	left := 0
	right := len(nums) - 1

	for left <= right {
		middle := (left + right) / 2
		if target > nums[middle] {
			left = middle + 1
		} else if target < nums[middle] {
			right = middle - 1
		} else {
			return middle
		}
	}

	return -1
}

区间左闭右开

package main

import (
	"fmt"
)

func main() {
	arr := []int{0, 1, 2, 3, 4, 5, 10}
	fmt.Println(binarySearch(arr, 10))
}

func binarySearch(nums []int, target int) int {
	left := 0
	right := len(nums)

	for left < right {
		middle := (left + right) / 2
		if target > nums[middle] {
			left = middle + 1
		} else if target < nums[middle] {
			right = middle
		} else {
			return middle
		}
	}

	return -1
}

Python

TODO