二分查找-704.二分查找-力扣(LeetCode)

一、题目分析

二、算法原理

解法一:暴力解法，遍历数组，一个元素一个元素的比对，时间复杂度为为O(N)

解法二:二分查找算法

这里只要满足“二段性”的数组都可以用二分查找。

这里可以不局限于找中间点，三分点，四分点等等都是可以的，不过，根据概率学的数学期望，二分点无疑是最好的。

回到我们的二分查找，我们需要以下几个变量，left(左区间),right(右区间),mid(二分点),会遇到三种情况，大于target，小于target，或等于target。

由于是循环进行的，所以我们还需要确定循环的条件。当left == right时，nums[mid]也是需要判断的，所以循环条件是left<=right，循环结束的条件则是left>right

二分查找的时间复杂度也可以计算出来O(logN)

到这里就可以根据上面的算法原理自己去实现一下，链接:704. 二分查找 - 力扣（LeetCode）

三、代码实例

这里的mid做了防溢出处理的，避免数据过大超过int，还有另一种形式int mid = left + (right - left+ 1)/2;这里加一操作对数据个数为奇数时没有影响，当数据为偶数时，二分点有两个，上面没加一的mid是靠近left的那个二分点，而加一的mid则是靠近right的按个二分点。

如果对您有帮助能否留下一个免费的赞，这将激励我继续创作，期待我们的下次再见！