一、算法描述
需求：在有序数组 A 内，查找值 target；如果找到返回索引，如果找不到返回 -1
1.描述
给定一个含 n 个元素的有序数组 A，满足 A0 ≤ A1 ≤ A2 ≤···≤ An-1，一个待查值 target。
2.解题思路
因为数组是有序的，所以用区间减半来提高查找效率，左区间起点i，右区间起点j，一开始是全部元素，每次拿中间的元素来和目标元素比较，如果相等则返回；
如果目标元素小于中间元素，则说明目标元素在左区间，直接把区间范围缩减到左区间。
如果目标元素大于中间元素，则说明目标元素在右区间，直接把区间范围缩减到右区间。
一直重复，直到找到目标元素。
3.解题步骤
- 1.设置
i= 0, j=n-1 - 2.如果
i > j，结束查找，没找到 - 3.设置
m = floor((i+j)/2)，m 为中间索引，floor 是向下取整(≤(i+j)/2的最小整数) - 4.如果
target < Am, 设置j = m - 1，跳到第2步 - 5.如果
target > Am, 设置i = m + 1，跳到第2步 - 6.如果
target = Am，找到了，结束查找。
二、使用左闭右闭
/**
* 二分查找基础版
* @param arr
* @param target
* @return
*/
public static int binarySearchBasic(int[] arr,int target) {
int i = 0;
int j = arr.length - 1;
while (i <= j) {
int mid = (i + j) / 2;
if (target < arr[mid]) {
// 去到左区间查找
j = mid - 1;
} else if (target > arr[mid]) {
// 去到右区间查找
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
判断的时候使用的是
i <= j，如果没有等于的话，那么参与比较的只有i和j中间的元素，i和j本身就没有参与比较，如果目标就是i和j，则会返回-1。
三、越界问题
当数组的数量达到了整数最大值个数的时候，使用(i+j)/2 运算，当要查找的目标在右区间时，运算的过程中i+j超过了整数的最大值，那么结果会变成负数。
在Java中，数字的表示都是带符号位的，虽然i+j已经超过了整数最大的表示范围，但(i+j)/2并没有超过，所以可以把除以2替换为右移运算，虽然i+j是负数，但是实际他对应的二进制数是没有问题的，只是在Java中，是带符号位的，所以就表现了负数，在使用右移替换了除法之后，得到的数就没有超过最大值了，就可以准确的转换为正确的数字了。
优化代码：
/**
* 二分查找基础版
* @param arr
* @param target
* @return
*/
public static int binarySearchBasic(int[] arr,int target) {
int i = 0;
int j = arr.length - 1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (target < arr[mid]) {
// 去到左区间查找
j = mid - 1;
} else if (target > arr[mid]) {
// 去到右区间查找
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
四、使用左闭右开
让j只作为边界，而不作为查找目标。
/**
* 二分查找基础版 左闭右开
* @param arr
* @param target
* @return
*/
public static int binarySearch(int[] arr,int target) {
int i = 0;
int j = arr.length; // 第一处不同
while (i < j) { // 第二处不同
int mid = (i + j) >>> 1;
if (target < arr[mid]) {
// 去到左区间查找
j = mid; // 第三处不同
} else if (target > arr[mid]) {
// 去到右区间查找
i = mid + 1;
} else {
return mid;
}
}
return -1;
}
注意：这里的判断，一定要使用<，不能是<=，因为j不作为比较的元素了，只作为边界，否则会在没有元素的情况下进入死循环。
五、平衡二分查找
在上面的写法中：
如果要查找的元素在最左边，那么判断中，只需要执行if判断，不需要执行else if判断，一共执行的次数是n次；
如果要查找的元素在最右边，那么判断中，if判断执行了，但是没满足，else if判断也执行，满足，所以一共执行的次数是2n次。
所以查找并不平衡。
优化思路：把多执行的else if判断抽出去，让每次操作都只执行一次判断，那么比较次数就不存在不平衡的情况了。
/**
* 平衡二分查找
* @param arr
* @param target
* @return
*/
public static int balanceBinarySearch(int[] arr, int target) {
int i = 0;
int j = arr.length;
while (j - i > 1) {
//当i和j中间还有元素的时候就继续
int mid = (i + j) >>> 1;
if (target < arr[mid]) {
j = mid;
} else {
i = mid;
}
}
if (arr[i] == target) {
return i;
} else {
return -1;
}
}
1.左闭右开的区间，i 指向的可能是目标，而 j 指向的不是目标
2.不在循环内找出目标对象，而是等范围内只剩i时，退出循环，在循环外比较 a[i] 与 target
3.循环内的平均比较次数减少了
4.时间复杂度
θ
(
l
o
g
(
n
)
)
θ(log(n))
θ(log(n))
缺点：无论什么情况，都要遍历完直到只剩下最终的元素，才会退出循环拿到结果。时间复杂度最好和最快都是 θ ( l o g ( n ) ) θ(log(n)) θ(log(n))
六、二分查找在Java中的实现
Arrays.binarySearch(int[] a, int key)
/**
* Searches the specified array of ints for the specified value using the
* binary search algorithm. The array must be sorted (as
* by the {@link #sort(int[])} method) prior to making this call. If it
* is not sorted, the results are undefined. If the array contains
* multiple elements with the specified value, there is no guarantee which
* one will be found.
*
* @param a the array to be searched
* @param key the value to be searched for
* @return index of the search key, if it is contained in the array;
* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
* <i>insertion point</i> is defined as the point at which the
* key would be inserted into the array: the index of the first
* element greater than the key, or <tt>a.length</tt> if all
* elements in the array are less than the specified key. Note
* that this guarantees that the return value will be >= 0 if
* and only if the key is found.
*/
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}
// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
七、二分查找对重复元素的处理
查找目标元素，如果有相同的元素，返回最左侧/最右侧的元素
/**
* 二分查找，返回最左侧的目标元素
* @return
*/
public static int binarySearchLeftMost(int[] arr, int target) {
int i = 0;
int j = arr.length - 1;
int candidate = -1 ;
while (i <= j) {
int mid = (i + j) >>> 1;
if (target < arr[mid]) {
// 去到左区间查找
j = mid - 1;
} else if (target > arr[mid]) {
// 去到右区间查找
i = mid + 1;
} else {
//相等了不立刻返回，而是找到最左侧的，再返回
candidate = mid;
//继续向左查找，看看是否还有相同的
j = mid - 1;
}
}
return candidate;
}
/**
* 二分查找，返回最右侧的目标元素
* @return
*/
public static int binarySearchRightMost(int[] arr, int target) {
int i = 0;
int j = arr.length - 1;
int candidate = -1 ;
while (i <= j) {
int mid = (i + j) >>> 1;
if (target < arr[mid]) {
// 去到左区间查找
j = mid - 1;
} else if (target > arr[mid]) {
// 去到右区间查找
i = mid + 1;
} else {
//相等了不立刻返回，而是找到最右侧的，再返回
candidate = mid;
//继续向左查找，看看是否还有相同的
i = mid + 1;
}
}
return candidate;
}
优化-1返回值：让找不到的时候，返回一个接近的元素下标，而不是-1
/**
* 优化最左查找返回值
* @param arr
* @param target
* @return 返回大于等于目标的最靠左的索引
*/
public static int binarySearchLeftMost1(int[] arr, int target) {
int i = 0;
int j = arr.length - 1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (target <= arr[mid]) {
// 去到左区间查找
j = mid - 1;
} else {
// 去到右区间查找
i = mid + 1;
}
}
return i;
}
/**
* 优化最右查找返回值
* @param arr
* @param target
* @return 小于等于目标的最靠右的索引
*/
public static int binarySearchRightMost1(int[] arr, int target) {
int i = 0;
int j = arr.length - 1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (target < arr[mid]) {
// 去到左区间查找
j = mid - 1;
} else {
// 去到右区间查找
i = mid + 1;
}
}
return i - 1;
}
八、Leetcode相关题目：
1.Leetcode704.二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
class Solution {
public int search(int[] nums, int target) {
int i = 0;
int j = nums.length -1 ;
while(i<=j){
int mid = (i+j) >>> 1;
if(target < nums[mid]){
j = mid -1;
}else if(target > nums[mid]){
i = mid +1;
}else{
return mid;
}
}
return -1;
}
}
2.Leetcode35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
class Solution {
public int searchInsert(int[] nums, int target) {
int i = 0;
int j = nums.length-1;
while(i<=j){
int mid = (i+j) >>> 1;
if(target<=nums[mid]){
j = mid -1;
}else {
i = mid +1;
}
}
return i;
}
}
3.Leetcode34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
class Solution {
public int[] searchRange(int[] nums, int target) {
// 查找最左侧元素
int left = searchMost(nums,target,-1);
if(left == -1){
return new int[]{-1,-1};
}else{
// 查找最右侧元素
int right = searchMost(nums,target,1);
return new int[]{left,right};
}
}
public int searchMost(int[] nums,int target,int lr){
int i = 0;
int j = nums.length - 1 ;
int candidate = -1;
while(i<=j){
int mid = (i+j) >>> 1;
if(target < nums[mid]){
j = mid -1;
}else if(target > nums[mid]){
i = mid + 1;
}else {
candidate = mid;
// 最左元素
if(lr == -1){
j = mid - 1;
}else{
//最右元素
i = mid + 1;
}
}
}
return candidate;
}
}
