二分查找

题目描述

题目如封面所示，在此再进行一定的解释

在一个给定了n个元素的数组（nums）中查找一个目标元素（target），该数组按升序排列，且元素全为整形。

要求：

  1. 如果找到了target，返回target的索引值
  2. 没找到，返回-1

解题思路及过程

暴力遍历

题目中所给出的条件已经非常清晰了，在第一遍做这道题的时候并没有注意到题目中所说的升序，于是第一遍就在纳闷，乱序的情况下怎么能用二分法呢？

当然也是有方法进行解决的，那就是直接把整个给定的数组全部遍历一遍，暴力求解，如果找到及返回，没找到返回-1.

具体实现：

1
2
3
4
5
6
7
8
9
10
11
class Solution{
public:
	int search(vector<int>& nums, int target){
        for(int i = 0; i < nums.size() ; i++){
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }    
}

时间复杂度：
$$
O（n）
$$
消耗内存30.8MB

相对来说，时间复杂度就是遍历整个数组所花费的N的元素的时间，比二分法要长。

二分查找

再写完第一个遍历之后，反过来继续思考二分法怎么解决乱序问题的时候，突然发现给定数组是升序的，于是恍然大悟。

总所周知，如果一个数列是升序或者降序的，你想从这个数列中找某个元素也就是target值，可以用这个值跟middle值进行一个对比，根据对比的结果进行数列的拆分。

总结有以下几种情况：

  1. target比middle大，那么区间从 [left, right] 缩小至 [middle, right]
  2. target比middle小，区间缩小至 [left, middle]
  3. target等于middle，直接返回

有了这个思路，那么就可以开始撰写代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
public:
	int search(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target){
                left = middle - 1;//因为target已经跟middle进行了比较，且不相等，所以左区间-1
            }
            else if(nums[middle] < target){
                right = middle + 1;//因为target已经跟middle进行了比较，且不相等，所以右区间+1
            }
            else{
                return middle;
            }
        }
        return -1;
    }    
}

时间复杂度：

$$
O（logn）
$$

内存占用30.68MB，在时间上进行了缩减。

总结

对于二分法而言，还需要注意一下其对于区间两个端点的取值情况，上述例子是默认左闭右闭的情况，还有左闭右开的情况，这个情况下需要注意middle值的更改，可以适当采用位运算。

二分法的重点就在于如何在比较之后进行区间的划分，并且要根据区间的不同定义进行不同边界处理。