题目解析
二分查找在数组有序可以使用,也可以在数组无序的时候使用(只要数组中的一些规律适用于二分即可)
704. 二分查找
算法讲解
当left >= right的时候,我们循环结束,但是当left和right缩成一个点的时候,我们最后这个点的大小是没有与target进行比较的,所以我们需要进行最后一次计较
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
int mid = (right - left) / 2 + 1;
while(left < right)
{
mid = left + (right - left) / 2;
if(target > nums[mid])
{
left = mid + 1;
}
else if(target < nums[mid])
{
right = mid - 1;
}
else return mid;
}
if(nums[left] == target)return left;
return -1;
}
};