二分法

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using UnityEngine;
/// <summary>
/// 二分查找算法(在有序数组中快速寻找一个指定数值)
/// </summary>
public class BinarySearchSort : MonoBehaviour
{
//有序数组
int[] array = new[] {5, 6, 7, 8, 9, 12, 45, 55};
void Start()
{
//调用查找方法,输出 bool值
Debug.Log(BinarySearch(array, 45));
}
/// <summary>
/// 二分查找方法
/// </summary>
/// <param name="array">数组</param>
/// <param name="targetNum">目标数值</param>
/// <returns>是否找到目标数值</returns>
bool BinarySearch(int[] array, int targetNum)
{
//起始点
int start = 0;
//结束点
int end = array.Length - 1;
//中界点
int mid;
//循环遍历(起始点<=终止点)
while (start <= end)
{
//计算中界点
mid = (start + end)/2;
//第一种情况
if (array[mid] > targetNum)
{
//终止点=中界点-1
end = mid - 1;
}
//第二种情况
else if (array[mid] < targetNum)
{
//起始点=中界点+1
start = mid + 1;
}
//找到
else
{
Debug.Log("所在下标:" + mid);
return true;
}
}
//未找到
Debug.Log("不存在该数值!");
return false;
}
}

文章目录
|