LeetCode704.二分查找

二分查找

学习内容

二分查找是在一个数组里，找一个target，判断这个target在不在数组中，在的话就返回这个target所在数组的下标。

二分查找有两个误区：

1. while的条件是小于还是小于等于-

• while(left <= right)
• while(left < right)

2. if后执行的语句是=mid还是等于mid-1

if(num[mid] > target){
  right = middle
   or 
  right = middle - 1
}

解决这两个误区的方式是：明确区间的定义。

看区间是左闭右闭（两边值都能取），还是左闭右开（只能取左边值），开始区间的定义，会影响到二分法的边界条件处理。

明确了区间定义后，接着就在while循环中坚持对区间条件的定义。

1. 左闭右闭区间

因为数组长度的有效值是0到size-1，而右边可以取到，所有初始设right为size-1。

left = 0; right = size-1;
while(left <= right){
  mid = (left+right)/2
  if num[mid] > target{
考虑左闭右闭的定义，右边界的范围可以是mid，也可以是mid-1。但是为了每一轮都能筛出来值，所以设置为mid-1
    right = mid - 1
  } else if nums[mid]<target{
左边可以取到mid、也可以是mid+1，为了每一轮更精确取到边界值，设置为mid+1
    left = mid + 1
  }
  else: return mid
}
return -1

2. 左闭右开区间

因为数组长度的有效值是0到size-1，而右边可以不能取到，所以初始设right为size。

left = 0; right = size;
while(left <= right){
  mid = (left+right)/2
  if num[mid] > target{
考虑左闭右开的定义，右边界的范围可以是mid、mid+1。但是为了每一轮都能筛出来值，所以设置为mid
    right = mid
  } else if nums[mid]<target{
左边可以取到mid、也可以是mid+1，为了每一轮更精确取到边界值，设置为mid+1
    left = mid + 1
  }
  else: return mid
}
return -1

代码

左闭右闭写法

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

go补充

for循环中多个变量的定义：

for i, j := 0, 0; i <= 5 && j <= 5; i, j = i+1, j-1 {
  t.Log("i: ", i)
  t.Log("j: ", j)
  sum += i + j
}

用for来代替while，初始变量在前面定义，for中写循环变量：

i := 0
for i < 5 {
  fmt.Println(i)
  i++
}

for中的变量用=，而不要用:=，不然会是局部变量，不改变for外面 的值。

参考：

1. 【GoLang】GoLang for 中有多个循环变量怎么处理？ https://www.cnblogs.com/junneyang/p/6072680.html
2. 弈心：网络工程师的Golang之路 -- for循环、while循环 https://zhuanlan.zhihu.com/p/574235761