什么是二分查找:二分查找每次只查询 mid(数组最中间的数),如果没找到目标,就缩小区间,根据 mid 和目标数对比,只搜左半区间或右半区间。
二分查找的前提:数据有序
二分查找结束的条件:查找区间为空,或者找到元素
二分查找的条件分支:
nums[mid]==target
nums[mid]<target
nums[mid]>target
二分查找的搜索区间表示形式:
- 左闭右开(区间为空的条件是 left==right)
- 左闭右闭(区间为空的条件是 left>right)
二分查找有的时候我会写出死循环来,仔细思考了一下:必须每次收缩边界的时候,都排除掉 mid,完全避免 mid 被重复查的可能。