数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Java二分查找程序
二分查找是一种快速的查找算法，其运行时间复杂度为O(log n)。该算法基于分治法的原理。为了使该算法正常工作，数据集合必须已排序。
二分查找通过比较集合中最中间的项来查找特定项。如果找到匹配项，则返回该项的索引。如果中间项大于该项，则在中间项左侧的子数组中搜索该项。否则，在中间项右侧的子数组中搜索该项。此过程也继续在子数组上进行，直到子数组的大小减小到零。
二分查找算法
以下是实现二分查找算法的步骤：
- 选择数组中的中间项，并将其与要搜索的关键值进行比较。如果匹配，则返回中间项的位置。
- 如果不匹配关键值，请检查关键值是否大于或小于中间值。
- 如果关键值更大，则在右子数组中执行搜索；但如果关键值小于中间值，则在左子数组中执行搜索。
- 迭代地重复步骤1、2和3，直到子数组的大小变为1。
- 如果关键值不存在于数组中，则算法返回搜索失败。
伪代码
以下是二分查找算法的伪代码：
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
Java二分查找程序
以下是使用Java实现二分查找算法的代码：
public class BinarySearch {
public static void main(String args[]){
int array[] = {10, 20, 25, 57, 63, 96};
int size = array.length;
int low = 0;
int high = size-1;
int value = 25;
int mid = 0;
mid = low +(high-low)/2;
while(low<=high){
if(array[mid] == value){
System.out.println(mid);
break;
}
else if(array[mid]<value)
low = mid+1;
else high = mid - 1;
}
mid = (low+high)/2;
}
}
输出
2
代码解释
这个Java程序在一个已排序的数组上执行二分查找，以查找特定值的索引。它初始化低索引和高索引，计算中间索引，并进入一个循环来将中间索引处的值与搜索值进行比较。循环调整低索引和高索引，直到找到搜索值，然后打印中间索引。该程序使用二分查找算法有效地查找索引。
更新于：2024年7月26日
2K+ 浏览量
广告