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;
}
}
程序基本上就是這樣了，其中注釋中有詳細的解釋說明