二分查找典型例题分析
二分查找基本知识
定义
二分搜索也称折半搜索，是一种在有序数组中查找某一个特定元素的搜索算法
特点
看似简单，写对很难
变形很多
面试中常用来考察code能力
运用前提
数组必须是排好序的
输入并不一定是数组，也可能是给定一个区间的起始和终止的位置
优点
时间复杂度为O(logn)，是一种非常高效的搜索
缺点
要求待查找的数组或区间是排好序的
若要求对数组进行动态地删除和插入操作并完成查找，平均复杂度会变为O(n)
采取自平衡的二叉查找树
可在O(nlogn)的时间内用给定的数据构建出一颗二叉查找树
可在O(logn)的时间内对数据进行搜索
可在O(logn)的时间内完成删除和插入的操作
应用
输入的数组或区间是有序的，且不会经常变动，要求从中找出一个满足条件的元素
核心思想
确定搜索的范围和区间
取中间的数判断是否满足条件
如果不满足条件，判定应该往哪个半边继续进行搜索
题目分类
基本概念
leetcode 704. 二分查找
找确定的边界
leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
找模糊的边界
leetcode 278. 第一个错误的版本
旋转数组查找
leetcode 33. 搜索旋转排序
二分查找代码实现
leetcode 704. 二分查找，这里就不分析了，直接上代码。
class Solution {public int search(int[] nums, int target) {if (nums.length == 0)return -1;int low = 0, high = nums.length - 1;while (low <= high){int mid = low + (high - low)/2;if (nums[mid] == target)return mid;else if (nums[mid] < target)low = mid + 1;elsehigh = mid - 1;}return -1;}}
二分查找（找确定的边界）
leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
题目：
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。
示例1:
输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]
示例2:
输入: nums = [5,7,7,8,8,10], target = 6输出: [-1,-1]
分析：
元素的第一个位置（上边界），这个位置要满足：
元素值等于目标值
该位置左边的一个数不是目标值
左边有数，那么该数必须小于目标值
左边没有数，那么该元素是数组的第一个元素
元素的最后一个位置（下边界），这个位置要满足：
元素值等于目标值
该位置右边的一个数不是目标值
右边有数，那么该数必须大于目标值
右边没有数，那么该元素是数组的最后一个元素
代码：
class Solution {public int[] searchRange(int[] nums, int target) {int[] res = {-1, -1};if (nums.length == 0)return res;res[0] = searchLowerRange(nums, target);res[1] = searchUpperRange(nums, target);return res;}public int searchLowerRange(int[] nums, int target){int low = 0, high = nums.length - 1;while (low <= high){int mid = low + (high - low)/2;if (nums[mid] == target){if (mid == 0 || nums[mid - 1] < target)return mid;elsehigh = mid - 1;} else if (nums[mid] < target){low = mid + 1;} else {high = mid - 1;}}return -1;}public int searchUpperRange(int[] nums, int target){int low = 0, high = nums.length - 1;while (low <= high){int mid = low + (high - low)/2;if (nums[mid] == target){if (mid == nums.length - 1 || nums[mid + 1] > target)return mid;elselow = mid + 1;} else if (nums[mid] < target){low = mid + 1;} else {high = mid - 1;}}return -1;}}
二分查找（找模糊的边界）
leetcode 278. 第一个错误的版本
题目：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。调用 isBadVersion(3) -> false调用 isBadVersion(5) -> true调用 isBadVersion(4) -> true所以，4 是第一个错误的版本。
分析：
第一个错误的版本，需要满足以下条件：
该版本是错误的版本
该版本的前一个版本是正确的版本
该版本是第一个版本（version = 1），那么该版本就是第一个错误的版本
该版本不是第一个版本（version > 1），那么该版本的前一个版本必须是正确的版本
代码：
/* The isBadVersion API is defined in the parent class VersionControl.boolean isBadVersion(int version); */public class Solution extends VersionControl {public int firstBadVersion(int n) {int low = 1, high = n;while (low <= high){int mid = low + (high - low)/2;if (isBadVersion(mid) == true && (mid == 1 || isBadVersion(mid - 1) == false))return mid;else if (isBadVersion(mid) == false)low = mid + 1;elsehigh = mid - 1;}return -1;}}
二分查找（旋转数组查找）
leetcode 33. 搜索旋转排序数组
题目：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3输出: -1
分析：
其实旋转过的排序数组也是由两部分排序数组组成的，用二分的思想来看，不管怎么去拆分这个数组，要么是左半部分是顺序数组，要么是右半部分是顺序数组。
在顺序数组中，很容易知道目标值target是否在这个区间里面。知道目标值target在这个区间里面，则在这个区间里面查找；反之在另外一个区间查找。
那怎么判断左半部分是顺序数组？只需要判断nums[low]和nums[mid]
nums[low]<=nums[high]
综上，思路如下：
nums[mid]等于target，返回结果
nums[mid]不等于target
左半部分是顺序
target在左半部分（nums[low] <= target < nums[mid]）
反之，target在右半部分
右半部分是顺序
target在右半部分（nums[mid] < target <= nums[high]）
反之，target在左半部分
代码：
class Solution {public int search(int[] nums, int target) {if (nums.length == 0)return -1;int low = 0, high = nums.length - 1;while (low <= high){int mid = low + (high - low)/2;if (nums[mid] == target)return mid;if (nums[low] <= nums[mid]){ //左边是顺序if (nums[low] <= target && nums[mid] > target)high = mid - 1;elselow = mid + 1;}else { //右边是顺序if (nums[mid] < target && nums[high] >= target)low = mid + 1;elsehigh = mid - 1;}}return -1;}}