使用二分查找法的前提(二分查找法)
使用二分查找法的前提(二分查找法)class Program { static void Main(string[] args) { var data = GetSS(4 0.00000001); Console.WriteLine(data*data); } /// <summary> /// 获取平方根 /// </summary> /// <param name="input">输入值</param> /// <param name="jd">精度</param> /// <returns></re
引入:二分法思想无处不在,我们经常玩的猜数字游戏,0-99的范围,最多需要多少次我就可以猜对呢?
使用二分法思想,最多仅仅需要7次就可以查找到。
二分法查找是非常恐怖的,以2的倍数缩小范围。所以时间复杂度O(logn)
局限性:1.针对二分法查找的数据必须是有序的。
2.二分法查找依赖于顺序表结构,也就是数组。因为二分法需要随机访问元素,也就是O(1)的复杂度找到对象,所以需要内存连续。如果使用链表,那么时间复杂度就会变得非常高
3.适合静态数据,不适合频繁的插入和删除操作的数据所以当数据比较静态,没有频繁的插入和删除的操作的时候,可以先对数据进行排序,排序时间复杂度最低O(nlogn)
例子:求一个数的平方根,可以指定精度。
从二分法的思想就是不断的范围缩减,所以代码实现上可以有通过递归的方式和非递归的方式实现。
class Program
{
static void Main(string[] args)
{
var data = GetSS(4 0.00000001);
Console.WriteLine(data*data);
}
/// <summary>
/// 获取平方根
/// </summary>
/// <param name="input">输入值</param>
/// <param name="jd">精度</param>
/// <returns></returns>
public static double GetSS(double input double jd)
{
double low = 0;
double high = input;
double middle = low (high - low) / 2;
while ((high - low) > jd)
{
if (input > middle * middle)
{
low = middle;
}
else
{
high = middle;
}
middle = low (high - low)/2;
Console.WriteLine(high - low);
}
return middle;
}
}
问题深入
上面的使用二分法查找都是最简单的情况,也就是数据不存在重复的情况下,但是数据如果存在重复的情况下,会出现其他的变种的需求;
(1)查找第一个元素等于给定值的元素
static void Main(string[] args)
{
var a = new[] { 1 2 8 8 8 8 8 8 11 13 18};
Console.WriteLine(GetValue(a a.Length 8));
}
public static int GetValue(int[] a int n int value)
{
var low = 0;
var high = n - 1;
while (low <= high)
{
int middle = low ((high - low) >> 1);
if (a[middle] > value)
{//因为不包含等于,可以多递增一个数
high = middle-1;
}
else if (a[middle] < value)
{
low =middle 1;
}
else
{
if (middle == 0 || a[middle - 1] != value)
{
return middle;
}
else
{
//因为是查找第一个所以将high赋值middle-1
high = middle-1;
}
}
}
return -1;
}
上面的代码就是当a[middle]=value的时候,需要判断一下middle-1的值是否是指定值。
(2)查找最后一个等于给定值的元素。
这个就比较简单了,只要在第一个的基础上稍作修改即可
public static int GetValue(int[] a int n int value)
{
var low = 0;
var high = n - 1;
while (low <= high)
{
int middle = low ((high - low) >> 1);
if (a[middle] > value)
{//因为不包含等于,可以多递增一个数
high = middle - 1;
}
else if (a[middle] < value)
{
low = middle 1;
}
else
{
if (middle == 0 || a[middle 1] != value)
{
return middle;
}
else
{
low = middle 1;
}
}
}
return -1;
}
(3)查找第一个大于等于给定值的元素
public static int GetValue(int[] a int n int value)
{
var low = 0;
var high = n - 1;
while (low <= high)
{
int middle = low ((high - low) >> 1);
if (a[middle] >= value)
{//因为不包含等于,可以多递增一个数
if (middle == 0 || a[middle - 1] < value)
{
return middle;
}
else
{
high = middle - 1;
}
}
else
{
low = middle 1;
}
}
return -1;
}
(4)查找最后一个小于等于给定值的元素
public static int GetValue(int[] a int n int value)
{
var low = 0;
var high = n - 1;
while (low <= high)
{
int middle = low ((high - low) >> 1);
if (a[middle] > value)
{//因为不包含等于,可以多递增一个数
high = middle - 1;
}
else
{
if (middle == 0 || a[middle 1] > value)
{
return middle;
}
else
{
low = middle 1;
}
}
}
return -1;
}