二分查找

704. 二分查找

要求：

1. 有序数组
2. 数组无重复

   使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

左闭右闭即[left, right]

l == r有意义，用于判断结果， 判断时必须 l <= r

// 左右闭
func search(nums []int, target int) int {
    l := 0
    r := len(nums) - 1 // 这里是个小细节，因为右边是闭区间，必须要取得到

    for l <= r  {
        mid := (l + r) >> 1
        x := nums[mid]
        if target == x {
            return mid
        }
        if target > x {
            l = mid + 1
        } else {
            r = mid -1
        }
    }
    return -1
}

左闭右开即[left, right)

l == r无意义， 判断只要 l < r
while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的

// 左闭 右开
func search(nums []int, target int) int {
    l := 0
    r := len(nums) // 这里是个小细节，因为右边是开区间，不用取到

    for l < r  {
        mid := (l + r) >> 1
        x := nums[mid]
        if target == x {
            return mid
        }
        if target > x {
            l = mid + 1 // 左开
        } else {
            r = mid // 右闭
        }
    }
    return -1
}

移除元素

27. 移除元素

双指针移位置

func removeElement(nums []int, val int) int {
    l := 0
    for r := 0; r < len(nums); r++ {
        if nums[r] == val {
            continue
        } else {
            nums[l] = nums[r] // 右边进行移动到左边
            l++
        }
    }
    return l
}

---

• 分类： 算法
• 标签： 算法基础 数组 二分查找