java二分查找算法代码
publicclass二分法递归查找{
publicstaticvoidmain(String[]args){
//定义数组,注意,二分查找数组必须是有序的数组!
int[]arr={1,3,5,7,9,11,13,15,17};
//接受查找后的返回值:索引值,如果没有则是-1;
//测试查找元素:9
inta=binary(arr,9,0,arr.length-1);
System.out.println("被查找数字索引位置在:"+a);
}
//参数列表依次为:被查找的数组,查找的数字,头索引,尾索引!
publicstaticintbinary(int[]arr,intkey,intstar,intend)//递归
{
//每次进来创建,中间索引值!
intmid=(star+end)/2;
//如果被查找数小于头,或者尾,或者头索引大于尾索引,则说明无该数,返回-1;
if(key<arr[star]||key>arr[end]||star>end){
return-1;
}
//如果中间值小于被查找数,则重新定义头索引移至中间+1位置,筛选掉一半数字!
if(arr[mid]<key){
//开始递归!
returnbinary(arr,key,mid+1,end);
//否则如果中间值大于被查找数,则重新尾索引移至中间-1位置,筛选掉一半数字!
}elseif(arr[mid]>key){
//开始递归!
returnbinary(arr,key,star,mid-1);
}else{
//否者就是找到了,返回该索引!
returnmid;
}
}
}
2. 二分查找 为什么 查找第一个数(7)是 会报异常:java.lang.StackOverflowError 各位大哥 看看下面代码
.二分法，首先要求，必须是有序的，
然后是 关于查不到结果的判断
如果 假设查找的是7，
依次查找的下标为 3，1，没找到。。。
出现了一种情况： centerIndex > rightIndex 悲剧 这下好了，下面情况 你输出一下 3个index你就知道咋回事儿了， 实际上是成了一个没有出口 的递归运算， 必然会出现溢出栈的情况。。。。
3. 什么是查找法
算法思想：
将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。
折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
算法步骤描述：
step1 首先确定整个查找区间的中间位置
mid = （ left + right ）/ 2
step2 用待查关键字值与中间位置的关键字值进行比较；
若相等，则查找成功
若大于，则在后（右）半个区域继续进行折半查找
若小于，则在前（左）半个区域继续进行折半查找
Step3 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。
折半查找的存储结构采用一维数组存放。
折半查找算法举例
对给定数列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。
折半查找的算法讨论：
优点: ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。
缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。
考虑：能否通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。……？
可以考虑把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的？实际上这就是分块查找的算法思想。
例如：[问题分析] 由于数据按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.
Java风格的代码举例：
//使用折半法进行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);
return nIndex;
}
二分查找的性能说明
虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O(n lg n) 的时间。
二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找
二分查找的C#实现代码：
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失败
}
static void Main(string[] args)
{
Console.WriteLine("请输入10个递增数字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("数字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("请输入一个你要查找的数字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}
分块查找又索引查找，它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L（一维数组）分成m个子表（要求每个子表的长度相等），且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表A。因此，分块查找的关键在于建立索引表A。
（1）建立索引表A（二维数组）
索引表包括两部分：关键字项（子表中的最大值）和指针项（子表的第一项在线性表L中位置）
索引表按关键字有序的。
例如：线性表L（有序）为：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3个子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二维数组：第一列为每个子表的最大值 ，第二列为每个子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，确定待查项X所在的子表（块）。
（3）在所确定的子表中可以用“折半查找”法搜索待查项X；若找到则输出X；否则输出未找到信息。
4. 如何用java代码实现在一个已排列好的数组中找出小于等于给定x的位数下标（用二分查找做）
importjava.util.Arrays;
importjava.util.Random;
publicclassTest{
publicint[]getRandom(intlen){
int[]nums=newint[len<=0?10:len];
Randomrandom=newRandom();
for(inti=0;i<nums.length;i++){
nums[i]=random.nextInt(100);
}
returnnums;
}
publicIntegergetIndex(int[]nums,intvalue,intstartIndex,intendIndex){
if(startIndex==endIndex){
returnstartIndex;
}
intindex=(startIndex+endIndex)/2;
if(nums[index]==value){
returnindex;
}elseif(startIndex+1==endIndex&&nums[endIndex]>value){
returnendIndex;
}elseif(nums[index]>value){
returngetIndex(nums,value,startIndex,index);
}else{
returngetIndex(nums,value,index,endIndex);
}
}
publicstaticvoidmain(String[]args){
Testtest=newTest();
intvalue=50;
intlen=10;
int[]nums=test.getRandom(len);
Arrays.sort(nums);
Integerindex=test.getIndex(nums,value,0,nums.length-1);
System.out.println(Arrays.toString(nums));
System.out.println(value);
System.out.println(index);
}
}
5. 用Java语言编写对整型数组进行二分查找的程序。
public class BinarySearchDemo {
public static void main(String[] args) {
int[] a = new int[]{1,5,7,9,11,18,23,48,69};
int point = new BinarySearchDemo().binarySearch(a, 23);
if(point == -1)
System.out.println("在数组中未查找到数23");
else
System.out.println("数字23是数组中第 " + (point + 1) + " 位数");
}
/**
* 二分法查找一个整数在整型数组中的位置
*
* 算法思路：首先得到数组a的最小值和最大值的下标，分别是：low和high，接着求出值位于数组中间那个数的下标middle
* 然后再将这个middle对应的数组中的数和待查找的数num进行比较，如果相等，则表示已查找到，如果num < a[middle]
* 则说明num位于a[low]和a[middle]之间，于是将a[middle - 1]设为较大值，继续求出此时对应的a[middle]，
* 再进行比较，其他情况可依次类推。一直到low=high，如果此时还没有在数组a中查找到，则说明该数组a中没有值num，返回-1
*
* @param a 给定的整型数组
* @param num 待查找的数 num
*
* @return 返回整数num在数组a中的位置下标，如果未查找到则返回-1
* */
public int binarySearch(int[] a,int num){
int low = 0;
int high = a.length - 1;
while(low <= high){
int middle = (low + high) / 2;
if(num == a[middle])
return middle;
else if(num < a[middle])
high = middle - 1;
else
low = middle + 1;
}
return -1;
}
}
程序基本上就是这样了，其中注释中有详细的解释说明