java二分法演算法

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

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

2. Java二分法

首先得告訴你，二分法的前提是必須是順序方式存儲，而且必須是排好序了的。比如要從100個數中查找某一個數，前提是這一百個數是排好序（這里假如從小到大）的，然後找到最中間的數，若最中間的數（這里是第50個）比你要找的這個數大那你只需要在1到49個數里找，然後再取最中間的數，再判斷，如此往復下去，最多次數，你算算看，

3. java 二分法 排序

二分排序就是用先用二分查找法來查某一個元素，然後再用別的排序演算法來進行排序。

package insert;

public class InsArrayApp {
public static void main(String[] args) {
int size = 100;
InsArray arr = new InsArray(size);

arr.insert(10);
arr.insert(9);
arr.insert(8);
arr.insert(7);
arr.insert(6);
arr.insert(10);
arr.insert(9);
arr.insert(8);
arr.insert(5);
arr.insert(4);
arr.insert(3);
arr.insert(2);
arr.insert(1);

arr.display();

// arr.insertSort();

// arr.display();

// System.out.println(arr.median());

// arr.noDups();

arr.noDups2();
arr.display();
}
}

class InsArray {
private int[] a;
private int nElems;

public InsArray(int size) {
a = new int[size];
nElems = 0;
}

public void insert(int value) {
a[nElems] = value;
nElems++;
}

public void display() {
for (int i = 0; i < nElems; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}

public void insertSort() {
int out, in;
int = 0;
int compare = 0;
/* for(out = 1;out<nElems;out++){
int tmp = a[out];
in = out;
while(in>0&&a[in-1]>=tmp){
a[in] = a[in-1];
--in;
}
a[in] = tmp;
}*/
for(out = 1;out<nElems;out++){
int tmp = a[out];
in = out;
while(in>0){
if(a[in-1]>=tmp){
a[in] = a[in-1];
--in;
++;
++compare;}
else{
break;
}
}
++compare;
a[in] = tmp;
}
System.out.println(":" + + "compare:" + compare);
}

public int median(){
insertSort();
int m = nElems/2;
return a[m];
}

public void noDups(){
insertSort();
/*
InsArray tmp = new InsArray(nElems);
for(int i = 0;i<nElems;i++){
for(int j = i+1;j<nElems;j++)
if(a[i] == a[j]){
a[j] = -1;
}
if(a[i]!=-1)
tmp.insert(a[i]);
}
*/
InsArray tmp = new InsArray(nElems);
int i;
for(int j = 0;j<this.nElems;j++){
/*if(tmp.nElems==tmp.find(this.a[j])) //binary find
tmp.insert(this.a[j]);
else
continue;*/
for( i = 0; i < tmp.nElems; i++) { // for each element
if(tmp.a[i]==this.a[j]) // found searchKey?
break;
}
if(i==tmp.nElems) // no
tmp.insert(this.a[j]);
}
this.a = tmp.a;
this.nElems = tmp.nElems;
}

public int find(long searchKey) {
int lowerBound = 0;
int upperBound = nElems-1;
int curIn;

while(true) {
curIn = (lowerBound + upperBound)/2;
if(a[curIn]==searchKey)
return curIn;
else if(lowerBound>upperBound)
return nElems;
else {
if(a[curIn]>searchKey)
upperBound = curIn-1;
else
lowerBound = curIn+1;
}
}
}

public void noDups2(){
insertSort();
for(int i = 0;i<nElems;i++){
for(int j = i+1;j<nElems;j++)
if(a[i] == a[j]){
a[j] = -1;
}
}
display();
int index = 0;
for(int i=0;i<nElems;i++){
if(a[i]!=-1){
index++;
}else{
for(int j=index+1;j<nElems;j++){
if(a[j]!=-1){
a[index] = a[j];
a[j]=-1;
index++;
break;
}
}
}
}
nElems = index;

}
}

上面的代碼，是我以前敲的，有個find()方法是二分查找，然後再用插入排序去進行排序。

4. Java基礎 遞歸二分法

如果都不滿足條件呢 可能你能確定一定會滿足其中一個 可是程序不能確定是不是一定會滿足其中一個 又不知道如果不滿足要返回什麼 所以報錯啦

5. JAVA 二分法

二分法的演算法一次查找剩下一半元素，那麼，最大比較次數，就是去到只剩下一個為止。
所以100除以2，除以幾次能小於等於1呢？
所以答案是7..

6. java計算2分法查找次數

2分法查找，前提是要有序，要排序，必然要比較大小，所以只要一個類它實現了Comparable介面的compareTo(T
o)方法（Comparable在java.lang包中）或是實現一個比較器對象介面Comparator(Comparator在java.util包)，都可以進行比較了。不管是String型,計本數據類型,還是其他什麼的，都可以用2分發查找了。給你看看API
java．util．Collections中2分法的API
binarySearch
public
static
<T>
int
binarySearch(List<?
extends
Comparable<?
super
T>>
list,
T
key)使用二分搜索法搜索指定列表，以獲得指定對象。在進行此調用之前，必須根據列表元素的自然順序對列表進行升序排序（通過
sort(List)
方法）。如果沒有對列表進行排序，則結果是不確定的。如果列表包含多個等於指定對象的元素，則無法保證找到的是哪一個。
此方法對「隨機訪問」列表運行
log(n)
次（它提供接近固定時間的位置訪問）。如果指定列表沒有實現
RandomAccess
介面並且是一個大型列表，則此方法將執行基於迭代器的二分搜索，執行
O(n)
次鏈接遍歷和
O(log
n)
次元素比較。
參數：
list
-
要搜索的列表。
key
-
要搜索的鍵。
返回：
如果搜索鍵包含在列表中，則返回搜索鍵的索引；否則返回
(-(插入點)
-
1)。插入點
被定義為將鍵插入列表的那一點：即第一個大於此鍵的元素索引；如果列表中的所有元素都小於指定的鍵，則為
list.size()。注意，這保證了當且僅當此鍵被找到時，返回的值將
>=
0。
拋出：
ClassCastException
-
如果列表中包含不可相互比較
的元素（例如，字元串和整數），或者搜索鍵無法與列表的元素進行相互比較。

7. 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();
}
}

8. 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;
		}
	}
}