使用二分查找的场景:

1. 数组是一个有序数组(一般的题目为升序或者非递减数组);

2. 题目一般会强调数组中无重复元素,因为一旦有重复元素,使用二分查找返回的元素下标可能是不唯一的;

3. 如果一道题涉及在数组中查找某个目标元素(target)的下标且要求时间复杂度是O(logn),此时可以考虑使用二分查找的方法.

使用二分查找的注意事项:

1. while循环语句中边界条件,是left < right 还是left <= right,一般如果是左闭右闭的区间,我们考虑写成left <= right,如果是左闭右开的情况下写成left < right (大部分题目中这两种区间出现的概率最大,左开右闭区间出现的频率很低,所以这里不做讨论);其实这里不需要记忆,只需要遵循一个原则,在左闭右闭或者左闭右开的时候,left和right能不能相等,或者说left = right的时候这个区间是否有效即可;

2.while循环体内left和right下标如何更新,写成right = mid - 1还是right = mid,一般当你while循环中的判断语句写成left <= right时,更新下标就用right = mid - 1,反之写成right = mid;

二分查找的两种写法:

法一(左闭右闭的区间):

区间的定义,决定了二分查找的代码如何书写,因为target在[left,right]区间,所以有:

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=;
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1.

public int binarySearch(int[] nums,int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;//这里为了防止left+right之后数据溢出if(nums[mid] < target) {left = mid + 1;} else if(nums[mid] > target) {right = mid - 1;} else {//找到返回下标return mid;}}//没有找到返回-1return -1;}

法二(左闭右开的区间):

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的;
• if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle].

public int binarySearch(int[] nums,int target) {int left = 0;int right = nums.length;//因为此时区间是左闭右开 所以right定义为数组的长度while (left < right) {int mid = left + (right - left) / 2;//这里为了防止left+right之后数据溢出if(nums[mid] < target) {left = mid + 1;} else if(nums[mid] > target) {right = mid;//因为是左闭右开的区间} else {//找到返回下标return mid;}}//没有找到返回-1return -1;}

LeetCode实例:

二分查找:给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题目链接:力扣

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while(left <= right) {int mid = (left + right) / 2;if(nums[mid] > target) {right = mid - 1;} else if(nums[mid] < target) {left = mid + 1;} else {return mid;}}return -1;} 
}