简介
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
算法要求
-
必须采用顺序存储结构。
-
必须按关键字大小有序排列。
代码实现
下面是不同的编程语言实现的算法参考
c# 代码
百度百科上算法实现有问题
/// <summary>
/// 二分查找法，只支持升序数组，数组内部为正整数，未找到返回 -1，
/// 找到返回目标值在数组中的索引值
/// </summary>
/// <param name="numArray">数组</param>
/// <param name="target">目标数字</param>
/// <returns>返回目标值在数组中的索引值</returns>
public static int BinarySearch(int[] numArray, int target)
{
if (numArray.Length == 0)
{
return -1;
}
// 数组起始和结束索引
int startIndex = 0;
int endIndex = numArray.Length - 1;
int searchCount = 0;
while (startIndex <= endIndex)
{
searchCount += 1;
// Console.WriteLine($"查找范围：{startIndex}-{endIndex}");
// int 类型相除会丢掉小数部分，获取的结果仍然是 int ,如 13/2=6 ，而不是6.5
int middleIndex = (startIndex + endIndex) / 2;
int middleValue = numArray[middleIndex];
if (target == middleValue)
{
Console.WriteLine($"查找了{searchCount}次");
return middleIndex;
}
else if (target > middleValue)
{
startIndex = middleIndex + 1;
}
else if (target < middleValue)
{
endIndex = middleIndex - 1;
}
else
{
}
}
Console.WriteLine($"查找了{searchCount}次");
return -1;
}遍历算法：
/// <summary>
/// 遍历查找
/// </summary>
/// <param name="numArray">数组</param>
/// <param name="target">目标数字</param>
/// <returns>返回目标值在数组中的索引值</returns>
public static int LoopSearch(int[] numArray, int target)
{
int searchCount = 0;
for (int index = 0; index < numArray.Length; index++)
{
searchCount += 1;
if (target == numArray[index])
{
Console.WriteLine($"查找了{searchCount}次");
return index;
}
}
Console.WriteLine($"查找了{searchCount}次");
return -1;
}测试：
static void Main(string[] args)
{
var numArray1 = new int[] { 1, 3, 6, 8, 9, 15, 26, 35, 36, 37, 38, 40, 42, 45, 46 };//15位数字
var numArray2 = new int[] { 1, 3, 6, 8, 9, 15, 26, 35, 36, 37, 38, 40, 42, 45 };//14位数字
var searchNum = 42;
var searchResult1 = BinarySearch(numArray1, searchNum);
var searchResult2 = BinarySearch(numArray2, searchNum);
var searchResult3 = LoopSearch(numArray1, searchNum);
var searchResult4 = LoopSearch(numArray2, searchNum);
Console.WriteLine($"searchResult1:{searchResult1}");
Console.WriteLine($"searchResult2:{searchResult2}");
Console.WriteLine($"searchResult3:{searchResult3}");
Console.WriteLine($"searchResult4:{searchResult4}");
}参考
发表评论