算法是计算机软件的基础，今年打算深入学习一些算法，记录一些算法理论以及最佳实践，希望可以坚持下去。

一、前言

数组是最基础的数据结构之一，二分查找数组是基本功，本文目的是深入学习数组以及二分查找数组算法的实战。

二、数组概念

关键点：

1、存储相同类型数据的序列。

2、数组在内存中是有序的。

三、二分查找数组实战

2分查找的基础是数组数据项是有序的，不管是增序还是降序都可以。

2分查找算法也是有技巧的，不希望以后是根据感觉写出来的或者写不出来，今天把技巧方法记录下来。

2分查找算法，首先需要确定搜索的合法左右边界，每次都取两个边界中间位置的数值和目标值进行比较

如果中间值大于目标值，则将右边界改成中间值如果中间值小于目标值，则将左边界改成中间值这样不断在缩小搜索范围，最终左边界右边界会接近直到右边界小于左边界。

以下面数组查找目标值9为例

1、确定合法搜索边界

确定合法边界前，我们需要约定数据的范围，我们以左闭右闭[]的原则约定搜索范围，也就是说要搜索的数据包括了左右边界。

int start = 0; int end = lenght-1;

怎么正确计算中位数？

可以推敲一下，使用start + (end - start) / 2 可以得到两个数的中位数

数组长度是偶数6 第一次计算中位数mid=start + (end - start) / 2 = 0+（5/2）= 3

此时索引3的数据项是5，比目标值小，那么数据位于mid 和 end之间 此时start = mid +1=4 为什么+1,因为mid位置的数不合法。

继续搜索。

第二次计算中位数=start + (end - start) / 2 = 4 +（1/2）= 4

到此找到了目标值。

class Solution { public int search(int[] nums, int target) { int start = 0; int end = nums.length - 1; //坚持合法数据在`左闭右闭[]`区间的原则 while(start <= end) { //在合法数据范围内查找 //找中位数 int mid = start + (end - start) / 2; if(nums[mid] == target) { return mid; } else if(nums[mid] > target) { end = mid - 1; //更新合法区间为 [start,mid-1],因为已知mid不合法 } else if(nums[mid] < target) { start = mid + 1; //更新合法区间为 [mid+1,end]，因为已知mid不合法 } } return -1; }}四、总结

二分查找是一个基础算法，希望以后遇到2分查找都可以根据本文的方法写出来，不是凭感觉做出来。

记住重要的原则，需要明确合法搜索数据的区间。本文是以左闭右闭原则来解决2分查找的问题。

时间复杂度分析

时间复杂度是O(logn),这里待补充时间复杂度的计算过程。