数据结构和算法-线性查找-二分查找
本文为joshua317原创文章,转载请注明:转载自joshua317博客 https://www.joshua317.com/article/130
一、二分查找简述
折半查找(Binary Search)又称为二分查找,其要求数据序列呈线性结构,也就是经过排序的数据序列。对于没有经过排序的数据序列,可以先进行排序操作,然后执行折半查找操作。它是一种效率较高的查找方法。但二分查找有一定的条件限制:要求线性表必须采用顺序存储结构,且表中元素必须按关键字有序(升序或降序均可)。
二、二分查找分析
折半查找的基本思路是:
在有序表中,取中间的记录作为比较对象
(1)如果要查找的值等于中间索引对应的值,则查找成功。
(2)若中间索引对应的值大于要查找的值,则在中间索引的前半部分继续查找。
(3)若中间索引对应的值小于要查找的值,则在中间索引的后半部分继续查找。
(4)不断重述上述查找过程,直到查找成功,或有序表中没有所要查找的值,查找失败。
具体操作过程如下:
现在我们有一个有序的整型数组listData,然后设置两个变量,一个是low,指向数组第1个索引的位置,即:low=0;另一个是high,指向数组最后一个索引的位置,即:high=listData.length-1。
设要查找的值为value。当low≤high时,反复执行以下步骤:
(1)计算中间索引的位置mid,mid=(low+high)/2。
(2)将待查找的值value和listData[middle]进行比较。
① 若listData[middle] == value,查找成功,middle所指元素即为要查找的元素。
② 若listData[middle] > value,说明若存在要查找的值,该值一定在查找有序数组的前半部分。修改查找范围的上界:high=middle-1,转(1)。
③ 若listData[middle] < value,说明若存在要查找的值,该值一定在查找有序数组的后半部分。修改查找范围的下界:low=middle+1,转(1)。
重复以上过程,当low>high时,表示查找失败。
接下来我们用图文的形式分下查找的过程:
现在有一组有序的整型数据为{2, 12, 15, 23, 25, 28, 39, 40,46,66}
若要查找value=39的记录,则折半查找过程如下。
(1)初始时
low=0;
high=9;
mid=(low+high)/2, middle=4;
listData[middle]=25;
(2)比较listData[middle]和value,由于listData[middle] < 46,下一步到后半部分查找,于是
low=middle+1,low=5;
high依旧为9, high=9;
mid=(low+high)/2, middle=7;
listData[middle]=40;
(3)比较listData[middle]和value,由于listData[middle] > 39,下一步到前半部分查找,于是
low依旧为5, low=5;
high=middle-1, high=6;
mid=(low+high)/2, middle=5;
listData[middle]=28;
(4)比较listData[middle]和value,由于listData[middle] < 39,下一步到后半部分查找,于是
low=middle+1,low=6;
high依旧为6, high=6;
mid=(low+high)/2,middle=6;
listData[middle]=39;
(5)比较listData[middle]和value,由于listData[middle] == 39,查找成功,返回索引,结束。
三、二分查找的实现
package com.joshua317;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
/*
System.out.println("折半查找算法实例");
System.out.println("请输入十个有序的整型数据");
int[] listData = new int[10];
Scanner scanner = new Scanner(System.in);
// 接收数据
for (int i = 0; i < listData.length; i++) {
listData[i] = scanner.nextInt();
}
// 打印所有数组元素
System.out.print("输入的数据为:");
for (int i = 0; i < listData.length; i++) {
System.out.print(listData[i] + ",");
}
System.out.println();
System.out.println("请输入要查找的数据");
int value = scanner.nextInt();
*/
int[] listData = {2, 12, 15, 23, 25, 28, 39, 40,46,66};
int value = 39;
int index = binarySearch(listData, value);
if (index != -1) {
System.out.println("在第" + (index+1) + "个位置,数据:" + listData[index]);
} else {
System.out.println("数据未找到");
}
}
public static int binarySearch(int[] listData, int value)
{
int low, middle, high;
low = 0;
high = listData.length - 1;
while (low <= high) {
middle = (low + high) / 2;
System.out.printf("low=%d,high=%d,middle=%d,listData[middle]=%d", low, high, middle, listData[middle]);
System.out.println();
if (listData[middle] == value) {
return middle;
} else if (listData[middle] > value) {
high = middle - 1;
} else if (listData[middle] < value) {
low = middle + 1;
}
}
return -1;
}
}
四、最后
折半查找的优点是比较次数较顺序查找要少,查找速度较快,执行效率较高。缺点是表的存储结构只能为顺序存储,不能为链式存储,且表中元素必须是有序的。折半查找成功时的平均查找长度log2(n+1)-1,它的时间复杂度为O(log2n)
本文为joshua317原创文章,转载请注明:转载自joshua317博客 https://www.joshua317.com/article/130
相关文章
- Python数据结构与算法 实现八大经典排序算法
- 初探语音识别ASR算法
- 【计算机视觉】基于样本一致性的背景减除运动目标检测算法(SACON)
- 【数组】数据结构与算法——代码随想录
- [数据结构与算法]二叉排序(搜索)树实现
- 【数据结构与算法】K 近邻算法—— KD 树 算法原理讲解和C语言实现代码
- 【数据结构与算法】用 golang 实现 LSM Tree 代码
- 基本数据结构和查找算法
- C++基础代码--20余种数据结构和算法的实现
- 算法竞赛入门经典(第二版) 习题训练
- LeetCode_贪心算法_简单_409.最长回文串
- 趣味算法图解,文科生都看懂了
- 【笔记】JavaScript版数据结构与算法——数据结构之“栈”(85. 最大矩形)。。。
- 【笔记】JavaScript版数据结构与算法——基础算法之“排序类”(41. 缺失的第一个正数)
- 【笔记】JavaScript版数据结构与算法——基础算法之“字符串类”(557.反转字符串中的单词 III、696.计数二进制子串)
- Java数据结构 遍历 排序 查找 算法实现
- 【数据结构与算法】希尔排序
- 【足迹C++primer】35、特定容器算法
- 算法 : 堆排序
- 【算法基础】(一)基础算法 --- 归并排序
- 【数据结构与算法】ArrayList与顺序表
- 【数据结构与算法】时间复杂度和空间复杂度
- 数据结构与算法 | 【二分查询】进阶与优化 ——区间查询、递归查询、0.618优化...
- 剪短的python数据结构和算法的书《Data Structures and Algorithms Using Python》