Go 每周一刷1.0

图片拍摄于2021年1月2日，舟山东极岛。

我说过了，会按照标签来刷题。每一个类别刷四到五题，分两篇文章，第一篇基础题，第二篇稍微变型的题。开篇就从二分开始吧。

Leetcode 704

这是一道最典型的二分基础题，从一个有序集合中查找目标值，还不需要考虑元素重复问题，那么就简单了。

func search(nums []int, target int) int {
  left, right := 0, len(nums)-1
  var mid int
  for left <= right {
    // mid = (left + right) / 2
    // 获取中位数
    mid = left + ((right - left) >> 1)
    // 如果中位数的值等于目标值，找到了，直接返回
    if nums[mid] == target {
      return mid
      // 如果当前中位数的值 > 目标值，说明值只可能存在中位数的左区间，
      // 并且不包括中位数
    } else if nums[mid] > target {
      right = mid - 1
      // 否则当前中位数的值 < 目标值，说明值只可能存在中位数的右区间,
      // 并且不包括中位数
    } else { 
      left = mid + 1
    }
  }
  return -1
}

值得注意的是求中位数的时候如果只是单纯的 mid = (left + right) / 2 ，那么当数字过大时相加会造成溢出，因此这里直接使用位运算。

上面的代码还不是很严谨，比如说，开头过个滤。

if len(nums) == 0 {
    return -1
  }

另外值得讨论的一点是 left <= right ，不少人会在这上面纠结到底是 < 还是 <=。这是因为理解的角度不同，就会有大同小异的解法，就会产生差异化的代码。只要能理解边界的问题，那么咋么写都不重要。但是我依然觉得，好的代码不单单是多么精简和高级的技巧，而是简单易懂。

left 和 right 都是数组的下标，他们代表的是当前查找的范围区间。在程序中通过判断的结果，来更新接下来要查找的区间是往左区间缩小还是右区间缩小。

那什么时候结束呢？

第一，程序已经找到结果了，那当然直接运行结束。

第二，没找到结果，不断的缩小区间，最后这个区间已经缩小成 0，没区间值了，也结束了。

现在你明白上面为什么要 <= 了吧。首先 left 肯定是不能大于 right 的，比如 [5,4] 这能是一个正常区间嘛。至于 = ，道理也很简单，[5,5] 这个区间还有一个公共的 5，如果漏掉，会导致程序出错。

Leetcode 34

这道题比刚才难度提高了一点，同样是查找目标值位置，我们需要返回两个值，一个值是目标值出现的第一个位置以及目标值出现的最后一个位置。

那我们上面还能用嘛？

改改就能用！

本质上对左右区间缩小的判断还是一样的道理。唯一不同的是，之前我们在查找到目标值之后就返回结果，现在不行了。我们得进一步确认目标值是不是对应第一个和最后一个的位置。

func searchRange(nums []int, target int) (res []int) {
  return append([]int{}, findFirstIndex(nums, target), findLastIndex(nums, target))
}

// 查找元素第一个
func findFirstIndex(nums []int, target int) int {
  var mid int
  left, right := 0, len(nums)-1
  for left <= right {
    //如果数字大会造成溢出
    // mid = (left + right)/2 
    //使用位运算
    mid = left + ((right - left) >> 1)
    // 如果当前中位数的值比目标值大，说明目标值只可能存在中位数的左区间(不包括中位数)
    if nums[mid] > target {
      right = mid - 1
      // 如果当前中位数的值比目标值小，说明目标值可能只可能存在中位数的右区间
    } else if nums[mid] < target {
      left = mid + 1
    } else { //说明 此时中位数的值等于目标值，但是不能确定它就是相同目标值的第一个
      //在相等的情况下，如果当前中位数索引处是0，或者当前中位数上一个索引位置的值不等于目标值，那肯定就它了，程序结束
      if mid == 0 || (nums[mid-1] != target) {
        return mid
      } else { //否则的话 肯定在左边，就往左区间再挤挤
        right = mid - 1
      }
    }
  }
  // 如果都没找到，那就返回-1
  return -1
}

// 查找元素最后一个
func findLastIndex(nums []int, target int) int {
  var mid int
  left, right := 0, len(nums)-1
  for left <= right {
    mid = left + ((right - left) >> 1)
    if nums[mid] > target {
      right = mid - 1
    } else if nums[mid] < target {
      left = mid + 1
    } else { //说明 此时中位数的值等于目标值，但是不能确定它就是相同目标值的最后一个
      //在相等的情况下，如果当前中位数索引处于最后一个位置，或者当前中位数下一个索引位置的值不等于目标值，那肯定就它了，程序结束
      if mid == len(nums)-1 || nums[mid+1] != target {
        return mid
      } else { //否则的话，肯定再右边 就往右区间再挤挤
        left = mid + 1
      }
    }
  }
  // 如果都没找到，那就返回-1 
  return -1
}

这期的题目就到这了，你有不一样的解法嘛？那么欢迎留言告诉我。代码放在:github.com/wuqinqiang/LeetCode-Go-...

本作品采用《CC 协议》，转载必须注明作者和本文链接