1、二分查找（binary search）
二分查找（binary search），也称折半搜索，是一种在 有序数组 中 查找某一特定元素 的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
- 时间复杂度:折半搜索每次把搜索区域减少一半，时间复杂度为O(log n)。（n代表集合中元素的个数）
- 空间复杂度: O(1)。虽以递归形式定义，但是尾递归，可改写为循环。
动图演示
二分查找
2、代码描述
递归
int binarysearch(int array[], int low, int high, int target) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (array[mid] > target)
return binarysearch(array, low, mid - 1, target);
if (array[mid] < target)
return binarysearch(array, mid + 1, high, target);
return mid;
}非递归（while循环）
int bsearchWithoutRecursion(int a[], int key) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] > key)
high = mid - 1;
else if (a[mid] < key)
low = mid + 1;
else
return mid;
}
return -1;
}3、二分查找中值的计算
这是一个经典的话题，如何计算二分查找中的中值？大家一般给出了两种计算方法：
- 算法一：
mid = (low + high) / 2 - 算法二：
mid = low + (high – low)/2
乍看起来，算法一简洁，算法二提取之后，跟算法一没有什么区别。但是实际上，区别是存在的。算法一的做法，在极端情况下，(low + high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。而算法二能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。
4、二分查找法的缺陷
二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。
数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是自平衡二叉查找树了，既能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。
5、练习题1
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
输出: 4https://leetcode.cn/problems/search-insert-position/?envType=study-plan-v2&envId=top-100-liked
</>代码
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left=0,right=n-1;
while(left<=right){
// int mid = (left+right)/2;
int mid = left + (right - left)/2;
// 目标数值在中间值 右边
if(target > nums[mid]){
left = mid+1;
// 目标数值在中间值 左边
} else if(target < nums[mid]){
right = mid-1;
}else {
return mid;
}
}
return left;
}
}6、练习题2
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
数据范围： ， 数组中任意值满足
进阶：时间复杂度 ，空间复杂度
示例1
输入：
[-1,0,3,4,6,10,13,14],13返回值：
6说明：
13 出现在nums中并且下标为 6示例2
输入：
[],3返回值：
-1说明：
nums为空，返回-1</>代码
import java.util.*;
public class Solution {
//nums是数组，target是目标值
public int search (int[] nums, int target) {
//定义了target在[left,right]区间内
int left = 0;
int right = nums.length-1;
//数组从小到大排序
while(right>=left){
//定义中间值的下角标
int middle = left + ((right-left)/2);
//如果中间值大于目标值，目标值在左半部分，下一轮二分查找[left,middle-1]
if (nums[middle] > target){
right = middle -1;
//如果中间值小于目标值，目标值在右半部分，下一轮二分查找[middle+1,right]
}else if(nums[middle] < target){
left = middle + 1;
//如果左右两边都没有，那就是中间值
}else {
return middle;
}
}
//没有找到目标值，返回-1
return -1;
}
}