单片机攻城之LeetCode刷题-704. 二分查找

今天刷的LeetCode编程题目是704. 二分查找，以下是学习笔记：

二分查找算法详解：
在升序数组nums 中寻找目标值target，对于特定下标i，比较nums[i] 和 target 的大小：
1、如果nums[i]=target，则下标i即为要寻找的下标；
2、如果nums[i]>target，则target 只可能在下标i的左侧；
3、如果 nums[i]<target，则target 只可能在下标i的右侧。
适用场景：在有序且不重复数组中查找目标值。

算例：

题目条件：
1、在一个有序（升序）数组nums中找出目标值target，并返回下标。
2、可以假设数组中所有元素不重复。

条件1保证了如果这个数组中存在目标值target，那么一定可以查找到目标值target并返回下标。假设这个数组是乱序的并且目标值target存在于前半部分（当然也可以假设目标值target在数组的后半部分），那么用二分法查找时有可能找不到，下面的例子可以说明这个问题：

条件2保证了查找结果返回唯一的下标。如果数组nums中存在目标值target，且有多个，那么程序将进入死循环。
例如：

void search(vector<int>& nums, int target) {
	int low = 0, high = nums.size() - 1, mid = 0;
	while (low <= high)
	{
		mid = low + (high - low) / 2;
		if (nums[mid] == target)
		{
			cout<< mid<<endl;
		}
		else if (nums[mid]<target)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	cout<< -1<<endl;
}
int main()
{
	vector<int> nums = {-1,0,3,5,9,9,12};
	search(nums, 9);
	//system("PAUSE");
	return 0;
}

以上代码在VS Professional 2015上的运行结果为无限打印数字5：

所以根据题目条件和二分查找算法的适用场景，LeetCode704. 二分查找C++题解代码如下：

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

参考文章：
https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-by-leetcode-solution-f0xw/
https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/
https://leetcode-cn.com/problems/binary-search/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-er-fe-ajox/