C++二分查找

1.算法

1.1 什么是算法

算法是一种解决问题的方法，它并不是一个新的知识点，而是讲我们学习过的知识点运用起来解决问题。

1.2 算法的时间复杂度

时间复杂度指的是算法所要执行的次数，而不是时间，我们学习的每个算法都会告知时间复杂度，但是目前我们先不学习如何计算算法的时间复杂度，以后再说。

2.二分查找

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

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

2.2 什么是二分查找

二分查找是一种高效的、方便的、简单的查找数据的方式，二分查找一般运用与有序序列中，这样才能进行二分查找。

2.3 二分查找的原理

我们先定义两个指针，分别指向数组的第一个和最后一个数的下标，我们在算出这两个指针之间的中间下标，定义为变量mid，如果mid的值比要查找的数大，那么就把右指针移动到mid-1的位置，如果小，就把左指针移动到mid+1的位置，如果相等，那么输出mid。

2.4 二分查找的模板

while(left < right)
{int mid = (left + right) / 2;if(arr[mid] > target)right = mid - 1;else if(arr[mid] < target)left = mid + 1;else{cout << mid << endl;break;}
}

注：二分查找的时间复杂度为O(Logn)。

2.5 参考答案

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){int mid = (left + right) / 2;if(nums[mid] == target)return mid;else if(nums[mid] > target)right = mid - 1;elseleft = mid + 1;}return -1;}
};

再见！