二分查找
概要
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
案例 1
请对一个有序数组进行二分查找{1，8，10，89，1000，1234}，输入一个数看看该数组是否存在次数，并且求出下标，如果没有就提示“没有这个数”。
思路
1.首先确定该数组中间的下标 mind = (left + right) /2;
2.然后让需要查找的数findval和array[mid]比较
- 2.1 findval > arr[mid],说明你要查找的数在mind的右边，因此需要递归的向右查找
- 2.2 findval < arr[mid],说明你要查找的数在mind的左边，因此需要递归的向左查找
- 2.3 findval == arr[mid] 说明找到，就返回
3.什么时候结束递归
（1）找到就结束
（2）递归完整个数组，仍然没有找到findval ，也需要结束递归当left > right 就需要退出
代码
internal class BinarySearch
{
//二分查找算法
/// <summary>
/// 初始化
/// </summary>
/// <param name="arr">数组</param>
/// <param name="left">左边索引</param>
/// <param name="right">右边索引</param>
/// <param name="findval">需要查找的值</param>
/// <returns>查找到的值下标，无就返回-1</returns>
public static int Search(int[] arr,int left,int right,int findval)
{
if (left > right)
{
return -1;
}
//当left > right时，说明整个数组没有找到
int mid = (left + right) /2;
int midval = arr[mid];
if (findval > midval)
{
//向右递归
return Search(arr, mid + 1, right, findval);
}
else if (findval < midval)
{
//向左递归
return Search(arr, left, mid - 1, findval);
}
else
{
return mid;
}
}
}调用
static void Main(string[] args)
{
//数组进行升序排序
int[] arr = { 1, 8, 10, 89, 1000, 1234 };
int result = BinarySearch.Search(arr, 0, arr.Length - 1, 89);
Console.WriteLine("Result =" + result);
Console.Read();
}
案例 2
{1,8,10,89,1000,1000,1234} 当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到奥，比如这里的1000.
思路
本例是二分查找算法
1.在找到mid值，不要马上返回
2.向mid索引值的左边扫描，将所有满足1000的元素的下标加入到一个集合中
3.向mid索引值的右边扫描，将所有满足1000的元素的下标加入到一个集合中
4.将list返回
public static List<int> Search0(int[] arr, int left, int right, int findval)
{
if (left > right)
{
return new List<int>();
}
//当left > right时，说明整个数组没有找到
int mid = (left + right) / 2;
int midval = arr[mid];
if (findval > midval)
{
//向右递归
return Search0(arr, mid + 1, right, findval);
}
else if (findval < midval)
{
//向左递归
return Search0(arr, left, mid - 1, findval);
}
else
{
List<int> resultIndexs = new List<int>();
//向mid索引值的左边扫描，将所有满足1000的元素的下标，加入到集合
int temp = mid - 1;
while (true)
{
if (temp < 0 || arr[temp] != findval)
{
break;
}
//否则就temp放入到list
resultIndexs.Add(temp);
//temp左移
temp -= 1;
}
//否则，就temp放入到list
resultIndexs.Add(mid);
temp = mid + 1;
while (true)
{
if (temp > arr.Length - 1 || arr[temp] != findval)
{
break;
}
//否则就temp放入到list
resultIndexs.Add(temp);
//temp左移
temp += 1;
}
return resultIndexs;
}
} static void Main(string[] args)
{
//数组进行升序排序
int[] arr = { 1, 8, 10, 89, 1000,1000, 1234 };
var result = BinarySearch.Search0(arr, 0, arr.Length - 1, 1000);
for (int i = 0; i < result.Count; i++)
{
Console.WriteLine(result[i]);
}
Console.Read();
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-05-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录