二分查找

二分查找

leetcode 链接

思路：

二分查找，可以使用两种区间方式，一种是左闭右开[left, right),一种是左闭右闭[left, right],这里使用左闭右开的区间方式。只要先记住一种即可。

typescript 解法

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const middle = Math.floor(left + (right - left) / 2); // 需要向下取整
    const value = nums[middle];
    if (target < value) {
      right = middle;
    } else if (target > value) {
      left = middle + 1; // 循环条件为闭的一边遍历判断后需要 + 1
    } else {
      return middle;
    }
  }
  return -1;
}

go 解法

func search(nums []int, target int) int {
    left := 0
    right := len(nums)
    for left < right {
        mid := left + (right - left) / 2 // go 语言中默认向下取整
        if target < nums[mid] {
            right = mid
        } else if target > nums[mid] {
            left = mid + 1
        } else if target == nums[mid] {
            return mid
        }
    }
    return -1
}