牛客网剑指offer之二分查找

前言：

 与牛客的相知相遇：

一次偶然的机会我接触到了牛客网，从那次我就发现牛客网好像是一个全能型的网站，里面有各种语言的练习题、算法题、大厂的面试题、还有求职等各项功能。从那以后我就开始了我的牛客之旅。

链接我就放在这了需要的伙伴们自取注册即可免费刷题

目录

二分查找

三个示例

问题描述

算法思想

构造实例

 代码实现

 1、递归

2、非递归

时间复杂度

---

二分查找

题目：

三个示例

问题描述

二分查找又称为折半查找，它要求待查找的数据元素必须是按关键字大小有序排列的。给定已排好序的n个元素s1,…,sn，现要在这n个元素中找出一特定元素x。 首先较容易想到使用顺序查找方法，逐个比较s1,…,sn，直至找出元素x或搜索遍整个序列后确定x不在其中。显然，该方法没有很好地利用n个元素已排好序这个条件。因此，在最坏情况下，顺序查找方法需要O(n)次比较。

算法思想

假定元素序列已经由小到大排好序，将有序序列分成规模大致相等的两部分，然后取中间元素与特定查找元素x进行比较，如果x等于中间元素，则算法终止；如果x小于中间元素，则在序列的左半部继续查找，即在序列的左半部重复分解和治理操作；否则，在序列的右半部继续查找，即在序列的右半部重复分解和治理操作。可见，二分查找算法重复利用了元素间的次序关系。

构造实例

 代码实现

 1、递归

//递归二分查找算法
int twoFind3(int A[], int k, int low, int high)
{
	int middle;
	if (low > high) return -1;//递归结束条件
	middle = (low + high) / 2;
	if (low==high && A[middle] == k) return middle;
	if (low < high) {
		if (A[middle] < k)      return  twoFind3(A, k, middle + 1, high);
		else  if(A[middle]==k)  return middle;
		else                    return  twoFind3(A, k, 0, middle - 1);
	}
	return -1;
}

2、非递归

int twoFind2(int A[], int len, int K)
{
	int low = 0, high = len - 1,middle;
	if (low > high) return -2;
	while (low < high)//不含等于的情况，并在最后做判断
	{
		middle = (low + high) / 2;
		if (K == A[middle]) return middle;
		else if (K > A[middle]) low = middle + 1;
		else high = middle - 1;
	}
	if (low == high && A[low] == K) return low;
	return -1;
}

时间复杂度

 写在最后：文章如若有什么错误或者不足的地方，欢迎各位指正。