前言：

 Encounter with Niu Ke：

一次偶然的机会我接触到了牛客网,From that time, I found that Niuke.com seems to be an all-around website,There are exercises in various languages、算法题、大厂的面试题、There are also functions such as job hunting.Since then, I have started my cattle journey.

I'll put the link here for those who need it to pick it up注册即可免费刷题

目录

二分查找

三个示例

问题描述

算法思想

构造实例

 代码实现

 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;
}

时间复杂度

 写在最后：If there are any errors or inadequacies in the article,欢迎各位指正.