二分查找——704. 二分查找

文章目录

• • 1. 题目
  • 2. 算法原理
  • • 2.1 暴力解法
    • 2.2 二分查找
  • 3. 代码实现

1. 题目

题目链接：704. 二分查找 - 力扣（LeetCode）

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
1
2
3

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
1
2
3

2. 算法原理

2.1 暴力解法

这里直接遍历整个数组进行查找，时间复杂度为O(N)，这里就不示例了。

2.2 二分查找

题目提到整个数组是有序的，这其实本质上这个数组有二段性

二段性：可根据规律，将这部分数组分为2部分，然后可以对其中一部分进行舍弃

这也是二分查找的本质

可以从各个位置来作为我们的划分点，但我们最多的还是选择1/2处

选择1/3或者1/4处是有概率一次性干掉超过一半的数的，但是数学统计发现，选择中间处时间复杂度是最好的

这里就分为三种情况，大于、小于和等于：

• 循环结束的条件：当left == right时，这里区间只有一个值，还是需要进行判断，一旦left>right这就说明这个值不存在
  所以循环的结束条件是left>right，在循环left<=right时，一直需要判断

• 时间复杂度：

  二次次数	区间
  1次	n/2
  2次	n/4
  3次	n/8
  4次	n/16
  x次	1

  这里第x次的时候，就可以写为 $$\frac{n}{2^x}$$ ，那这里的x就是logN

3. 代码实现

class Solution {
public:
    int search(vector& nums, int target)
    {
        int left = 0;
        int right = nums.size()-1;
        while(left<=right)
        {
            int midi = left + (right-left)/2;	//防止溢出
            if(nums[midi]target)
            {
                right = midi-1;
            }
            else
            {
                return midi;
            }
        }
        return -1;    
    }
};
                return midi;
            }
        }
        return -1;    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31