java實現二分查找演算法

Ⅰ java二分查找

我大概看了一下,找出了你2個重要的缺點.
第一,你用一個5個數的小數組挨個按你寫的演算法算一下,你會發現很多地方是a.length-1而非a.length,有的地方是==,而不是>.
其中還有2個小地方.
if(count>a.length/2) break;
可以寫成while(reader.hasNextInt()&&count<a.length/2).
3.else if(n<a[middle]) 可以寫成 else.
第二,是最重要的問題.演算法上面.
試想一下如果只有2個數.start是0,end是1,給出的數是a[end],用你的if(n>a[middle]) start=middle;0.5取0,永遠start,middle都是0.如果你說因此你用a.length而不是減1,那a[start]就永遠也取不到。
怎麼解決,加一個如果middle=(start+end)/2後等於start且不為0的話,start取end.

Ⅱ 怎麼計算java二分法查找的比較次數

您好，我來為您解答：
演算法：當數據量很大適宜採用該方法。採用二分法查找時，數據需是有序不重復的。
基本思想：假設數據是按升序排序的，對於給定值
x，從序列的中間位置開始比較，如果當前位置值等於
x，則查找成功；若
x
小於當前位置值，則在數列的前半段中查找；若
x
大於當前位置值則在數列的後半段中繼續查找，直到找到為止。
希望我的回答對你有幫助。

Ⅲ 用java寫二分搜索，要求數組是由用戶輸入，再輸入時，數組是無序的，要對數組進行從小到大的排序

二分查找又稱折半查找，它是一種效率較高的查找方法。
【二分查找要求】：1.必須採用順序存儲結構 2.必須按關鍵字大小有序排列。

/**
* 二分查找又稱折半查找，它是一種效率較高的查找方法。
【二分查找要求】：1.必須採用順序存儲結構 2.必須按關鍵字大小有序排列。
* @author Administrator
*
*/
public class BinarySearch {
public static void main(String[] args) {
int[] src = new int[] {1, 3, 5, 7, 8, 9};
System.out.println(binarySearch(src, 3));
System.out.println(binarySearch(src,3,0,src.length-1));
}

/**
* * 二分查找演算法 * *
*
* @param srcArray
* 有序數組 *
* @param des
* 查找元素 *
* @return des的數組下標，沒找到返回-1
*/
public static int binarySearch(int[] srcArray, int des){

int low = 0;
int high = srcArray.length-1;
while(low <= high) {
int middle = (low + high)/2;
if(des == srcArray[middle]) {
return middle;
}else if(des <srcArray[middle]) {
high = middle - 1;
}else {
low = middle + 1;
}
}
return -1;
}

/**
*二分查找特定整數在整型數組中的位置(遞歸)
*@paramdataset
*@paramdata
*@parambeginIndex
*@paramendIndex
*@returnindex
*/
public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){
int midIndex = (beginIndex+endIndex)/2;
if(data <dataset[beginIndex]||data>dataset[endIndex]||beginIndex>endIndex){
return -1;
}
if(data <dataset[midIndex]){
return binarySearch(dataset,data,beginIndex,midIndex-1);
}else if(data>dataset[midIndex]){
return binarySearch(dataset,data,midIndex+1,endIndex);
}else {
return midIndex;
}
}

}

Ⅳ JAVA 二分查找

,在將100/。;2/2與20比較.collections，取一段已經排好序的數據段，不過由於針對必須是已經排好序的數據段進行操作.util。直到找出20，集合）進行操作的方法大多都封裝與java，有1-100數據，20<，推薦冒泡法
java中對數據段（數組二分查找原理，java開源，此方法操作速度較快;類下邊，也可以與我進行交流，qq，首先將100/2與20比較，演算法相當之精闢，依此類推
如;100/，需要查找20，樓主有興趣可以去看看他的源碼，用需要查找的數據與該數據段的1/。，使用較少;2處的數據進行比較;2，先將該數據段從中間切割開

Ⅳ 什麼叫java中的二分查找法

1、演算法概念。

二分查找演算法也稱為折半搜索、二分搜索，是一種在有序數組中查找某一特定元素的搜索演算法。請注意這種演算法是建立在有序數組基礎上的。

2、演算法思想。

①搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；

②如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

③如果在某一步驟數組為空，則代表找不到。

這種搜索演算法每一次比較都使搜索范圍縮小一半。

3、實現思路。

①找出位於數組中間的值，並存放在一個變數中（為了下面的說明，變數暫時命名為temp）；

②需要找到的key和temp進行比較；

③如果key值大於temp，則把數組中間位置作為下一次計算的起點；重復① ②。

④如果key值小於temp，則把數組中間位置作為下一次計算的終點；重復① ② ③。

⑤如果key值等於temp，則返回數組下標，完成查找。

4、實現代碼。

/**
*description:二分查找。
*@paramarray需要查找的有序數組
*@paramfrom起始下標
*@paramto終止下標
*@paramkey需要查找的關鍵字
*@return
*/
publicstatic<EextendsComparable<E>>intbinarySearch(E[]array,intfrom,intto,Ekey)throwsException{
if(from<0||to<0){
("paramsfrom&lengthmustlargerthan0.");
}
if(from<=to){
intmiddle=(from>>>1)+(to>>>1);//右移即除2
Etemp=array[middle];
if(temp.compareTo(key)>0){
to=middle-1;
}elseif(temp.compareTo(key)<0){
from=middle+1;
}else{
returnmiddle;
}
}
returnbinarySearch(array,from,to,key);
}

Ⅵ 如何用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);

}

}

Ⅶ java泛型 二分查找

以下代碼是關於對象的 二分查找 的例子，已經測試通過，執行即可。
Student 是基本比較對象類
Dichotomy 是二分法執行類
Test 是測試類

package com.dichotomy;

public class Student implements Comparable<Student> {

private int id;
private String name;
private String idCard;
private String sex;
private String mobile;

public int getId() {
return id;
}

public void setId(int id) {
this.id = id;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public String getIdCard() {
return idCard;
}

public void setIdCard(String idCard) {
this.idCard = idCard;
}

public String getSex() {
return sex;
}

public void setSex(String sex) {
this.sex = sex;
}

public String getMobile() {
return mobile;
}

public void setMobile(String mobile) {
this.mobile = mobile;
}

/**
* 排序控制
* @param o1 Student
* @param o2 Student
* @return int 返回 -1 向前移動, 1 向後移動, 0 不移動
* 這個方法需要自己進行調整，排序比較和二分查找時均使用此方法進行位置調整
* 比較時使用的key自己可以進行修改，不過要保證唯一性，否則查詢出來的值會不準確
*/
public int compareTo(Student o) {

//不同的執行次序決定排序和查找次序不同,可以同下面的調換一下
if(this.getId() < o.getId()){
return -1;
} else if(this.getId() == o.getId()){
;
} else {
return 1;
}

//不同的執行次序決定排序和查找次序不同
int c = this.getIdCard().compareTo(o.getIdCard());
if(c != 0){
return c;
}

//不同的執行次序決定排序和查找次序不同
int n = this.getName().compareTo(o.getName());

if(n != 0){
return n;
}

return 0;
}

public String toString(){
StringBuffer sb = new StringBuffer();
sb.append(this.getId()).append("\t");
sb.append(this.getName()).append("\t");
sb.append(this.getIdCard()).append("\t");
sb.append(this.getMobile()).append("\t");
sb.append(this.getSex());
return sb.toString();
}
}

Ⅷ java二分法查找的遞歸演算法怎麼實現

什麼是二分查找？

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

二分查找優缺點

優點是比較次數少，查找速度快，平均性能好；

其缺點是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件：查找序列是順序結構，有序。

過程

首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

利用循環的方式實現二分法查找

public class BinarySearch {
public static void main(String[] args) {
// 生成一個隨機數組 int[] array = suiji();
// 對隨機數組排序 Arrays.sort(array);
System.out.println("產生的隨機數組為： " + Arrays.toString(array));

System.out.println("要進行查找的值： ");
Scanner input = new Scanner(System.in);
// 進行查找的目標值 int aim = input.nextInt();

// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);

}

/** * 生成一個隨機數組 *
* @return 返回值，返回一個隨機數組 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之間的隨機數 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環遍歷為數組賦值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}

/** * 二分法查找 ---循環的方式實現 *
* @param array 要查找的數組 * @param aim 要查找的值 * @return 返回值，成功返回索引，失敗返回-1 */
private static int binarySearch(int[] array, int aim) {
// 數組最小索引值 int left = 0;
// 數組最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找數值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍 if (aim < array[mid]) {
right = mid - 1;
// 若查找數值比中間值大，則以整個查找范圍的後半部分作為新的查找范圍 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找數據與中間元素值正好相等，則放回中間元素值的索引 } else {
return mid;
}
}
return -1;
}}
運行結果演示：

總結：

遞歸相較於循環，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~

Ⅸ 用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;
}

}

程序基本上就是這樣了，其中注釋中有詳細的解釋說明

Ⅹ 用java 編寫一個 數組排序之後用2分法查找特定的對象。

二分查找演算法 - 當中間值小於要找的值時，從leftIndex找到midindex-1； 當中間值大於要找的值時，從midIndex+1找到rightIndex。下面給你一個二分法的代碼，你應該可以看懂

publicclassDemo8{
publicstaticvoidmain(String[]args){
intarr[]={2,6,8,9,25,26,28,35,40};
Testt=newTest();
t.find(0,arr.length-1,35,arr);
}
}
classTest{
publicvoidfind(intleftIndex,intrightIndex,intval,intarr[]){
intmidIndex=(leftIndex+rightIndex)/2;
intmidval=arr[midIndex];
if(midval==val){
System.out.println("找到index為："+midIndex);
}
elseif(midval>val){
find(leftIndex,midIndex-1,val,arr);
}
elseif(midval<val){
find(midIndex+1,rightIndex,val,arr);
}
}
}