博客

题目来源于力扣——

704. 二分查找 – 力扣（LeetCode） (leetcode-cn.com)

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

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2

输出: -1

解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。

n 将在 [1, 10000]之间。

nums 的每个元素都将在 [-9999, 9999]之间。

我们如何实现快速查找呢，有些朋友可能会想到遍历数组，但如果这个数组很大，有几百上千个元素呢，为了让计算机减少不必要的运算，我们可以运算跟简单的方法。

这个方法就是二分查找：

就拿一个简单的数组来做一下说明吧：

假设有一个数组arr[10]={1,2,3,4,5,6,7,8,9}   ,然后假设我们要查找的元素是7;

我们可以先将一个数组分成两半，如果要查找的数字大于中间的元素，那很明显要查找的数字肯定在数组的左半边，右半边的元素就可以不去管它了。这里我们要查找的元素是7，这个数组中间元素是5，这是一个有序数组，5都比7小了，5左边的元素肯定是不用考虑的了。

这时我们可以把5认为是数组第一个元素，中间元素就变为了7，这时候我们就找到了要找的元素7，如果要找的元素是8重复上面步骤既可以了。

下一步就是中间元素变成7，就找到了

代码如下：

#include<stdio.h>
int search(int arr[10], int sz,int target)
{
	int right = sz - 1;    //数组最后一个元素的下标
	int left = 0;          //数组第一个元素的下标
	while (left < right)   //left>right时，停止循环
	{
		int mid = (right + left) / 2;      //计算中间元素的下标
		if (arr[mid] < target)             //中间元素5<7
		{           
			left = mid +1;                //当大于或下于中间元素下标时中间元素也不用考虑了
		} 
		else if (arr[mid] > target)        
		{
			right = mid-1;               
		}
		else
		{
			return mid;                   //如果要查找的数就是中间元素的下标，直接返回
		}
	}
		
	if (left > right)
	{
		return -1;
	}
	
}
int main()
{
	int arr[10] = {1,2,3,4,5，6,7,8,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);   //计算数组元素个数
	int target = 7;    //要查找的目标
	int ret=search(arr, sz,target);
	if (ret >= 0)
	{
		printf("要查找元素的下标是：%d", ret);
	}
	else
	{
		printf("下标不存在\n");
	}
}