二分查找

算法思路

二分查找是在数组中查找元素是常用的的一个基础算法，他每次查询数组中一个特定段落中最中间的元素是否符合条件，若不符合则将其作为新的边界进行下一次查找。二分查找可以将原本遍历查询所需的的时间复杂度从O(n)降到O(log n)。

可以进行二分查找的前提是==数组是一个有序数组==并且==数组中没有重复元素==，当数组中存在重复元素时算法返回的查询结果就不再是唯一的。当符合这两个条件时就说明可以使用二分查找来解决问题，否则可能需要重新考虑一下是否采用二分查找。

下面简单画一下二分查找的流程图：

二分查找流程图

对于二分查找，其难点为控制好边界条件，因为其查找过程中肯定离不开左右边界。而边界条件最常用的即左闭右开[left, right)和左闭右闭[left, right]，他们所对应的循环条件即while(left < right)和while(left <= right)，确定边界时的区别即为右边界是否需要额外减一（闭区间需要减一，开区间不需要，因为开区间无法达到右边界）。

例题1

704. 二分查找 - 力扣（LeetCode）。

给定一个 n 个元素==有序的（升序）==整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。必须编写一个具有 O(log n) 时间复杂度的算法。

当输入nums = [-1,0,3,5,9,12], target = 9时，target在数组中的位置为4，所以返回4.

提示：

你可以假设 nums 中的==所有元素是不重复的==。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

题目提到数组有序并且元素不会重复，那么它就是一个标准的可以用二分查找解决的问题（虽然题目已经写了叫做二分查找）。

这里采用左闭右闭的解法，即确定左边界为下标0处，右边界为数组末尾。对左右边界进行判定，直到找到符合条件的元素或者两个边界重合为止（没有该元素），以示例1为例，他的查找流程如下：

例题1

代码如下：

public class Solution {
    public int Search(int[] nums, int target) {
        if(nums.Length<=0)return -1;	// 当数组长单独为0时，直接返回-1
        int left = 0;
        int right = nums.Length-1;		// 分别设置左右边缘下标
        if(nums[right] > target || nums[left] < target) return -1;	// 当最大值小于目标值或最小值大于目标值时直接返回-1
        while(right >= left){			// 左右边界有效
            int middle = (right - left) / 2 + left;		// 获取中间下标
            if(nums[middle] == target) return middle;	// 找到target
            else if(nums[index] < target) left = middle + 1;	//比target小，将中间下标+1定位左边界
            else right = index - 1;					// 将中间下标定为右边界
        }
        return -1;									// 没有找到
    }
}

例题2

力扣 35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

当输入为nums = [1,3,5,6], target = 5时，因为5已经在数组内，直接返回其下标；而当target = 2时，因为他不存在于数组内，所以返回按顺序插入的位置也就是 1 和 3 之间。

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的升序排列数组
-104 <= target <= 104

这道题也是一个标准的可以使用二分查找的题目，并且在题目中明确写了需要使用时间复杂度为 O(log n) 的算法。但可能会有人会出现疑问，这道题是寻找插入位置，而二分查找是寻找元素在数组中所在的位置，这里不一样怎么用二分来解决呢？其实他们的本质是一样的。

在二分查找中，我们确实主要用来寻找元素所在位置，但他的算法逻辑已经将元素所在范围一步一步缩小直到缩小到一个特定的位置，这个位置就是元素所在位置或者应该插入的位置。这里放一下使用闭区间二分查找情况在这里：

例题2

可以看见数组中并没有该元素，但是左右指针都确定到了一个位置，这个位置恰好是需要寻找的target插入的位置前一个下标，也就是说当前的middle = left = right，那么此时需要返回的下标即为middle + 1位置。而在二分查找算法中，当我们找到的中间元素小于target时，我们会将左指针移动到该元素右侧，在这种情况下左指针刚好处于需要插入的位置，并且不满足继续循环条件不会再进行移动，也就是说，最后只需要返回左指针的位置，他就是插入的位置。

完整的代码如下：

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        // 设置左右指针
        int left = 0;
        int right = nums.Length - 1;
        int middle =0;
        
        // 闭区间循环判定
        while(left <= right){
            // 获取中间元素下标
            middle = left + (right - left) / 2;
            // 对元素大小进行判定
            if(nums[middle] > target) right = middle - 1;
            else if(nums[middle] < target)left = middle + 1;
            else return middle;	// 找到target，返回对应下标
        }
        // 循环结束说明不含有target，直接返回插入位置
        return left;
    }
}

二分查找

二分查找

算法思路

例题1

例题2

相关建议