java二分查找算法代碼 java二分法查找算法

關(guān)于java的binarySearch（）方法

結(jié)果是-6的原因是在子串[2,3,4,5,6]中并未找到8這個數(shù)字。然后我們來看一下binrySearch的源碼

成都創(chuàng)新互聯(lián)2013年至今，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元福安做網(wǎng)站,已為上家服務(wù),為福安各地企業(yè)和個人服務(wù),聯(lián)系電話:028-86922220

public static int binarySearch(int[] a, int fromIndex, int toIndex,

int key) {

rangeCheck(a.length, fromIndex, toIndex);

return binarySearch0(a, fromIndex, toIndex, key);

}

private static int binarySearch0(int[] a, int fromIndex, int toIndex,

int key) {

int low = fromIndex;

int high = toIndex - 1;

while (low = high) {

int mid = (low + high) 1;

int midVal = a[mid];

if (midVal key)

low = mid + 1;

else if (midVal key)

high = mid - 1;

else

return mid; // key found

}

return -(low + 1); ?// key not found.

}

可以從源碼中看到，真正的二分查找是在binarySearch0方法中進(jìn)行的。每次循環(huán)都會計(jì)算出本輪的中間位置mid，以及獲取中間值midVal。當(dāng)中間值小于key時，說明要找的值在右半邊，low等于mid+1，當(dāng)中間值大于key說明在左半邊，high=mid-1,找到了然后開始下一輪。當(dāng)?shù)扔跁r也就是找到了目標(biāo)值，直接返回位置mid。如果最后找不到目標(biāo)值，則返回-(low+1)。

再來看看具體問題的執(zhí)行：

第一輪算出的mid是(1+5) 1 =2，midValue=3 8 ,low=3；

進(jìn)入第二輪mid為（3+5）1? =3,midValue=4 8 ,low=4；

進(jìn)入第三輪mid為（4+5）1 = 4，midValue=5 8,low=5; 此時low==high跳出while循環(huán) 返回-（5+1）即-6.

拓展知識

二分查找的流程如下圖：

java泛型 二分查找

以下代碼是關(guān)于對象的 二分查找 的例子，已經(jīng)測試通過，執(zhí)行即可。

Student 是基本比較對象類

Dichotomy 是二分法執(zhí)行類

Test 是測試類

package com.dichotomy;

public class Student implements ComparableStudent {

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 不移動

* 這個方法需要自己進(jìn)行調(diào)整，排序比較和二分查找時均使用此方法進(jìn)行位置調(diào)整

* 比較時使用的key自己可以進(jìn)行修改，不過要保證唯一性，否則查詢出來的值會不準(zhǔn)確

*/

public int compareTo(Student o) {

//不同的執(zhí)行次序決定排序和查找次序不同,可以同下面的調(diào)換一下

if(this.getId() o.getId()){

return -1;

} else if(this.getId() == o.getId()){

;

} else {

return 1;

}

//不同的執(zhí)行次序決定排序和查找次序不同

int c = this.getIdCard().compareTo(o.getIdCard());

if(c != 0){

return c;

}

//不同的執(zhí)行次序決定排序和查找次序不同

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中的二分查找法

1、算法概念。

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

2、算法思想。

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

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

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

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

3、實(shí)現(xiàn)思路。

①找出位于數(shù)組中間的值，并存放在一個變量中（為了下面的說明，變量暫時命名為temp）；

②需要找到的key和temp進(jìn)行比較；

③如果key值大于temp，則把數(shù)組中間位置作為下一次計(jì)算的起點(diǎn)；重復(fù)① ②。

④如果key值小于temp，則把數(shù)組中間位置作為下一次計(jì)算的終點(diǎn)；重復(fù)① ② ③。

⑤如果key值等于temp，則返回?cái)?shù)組下標(biāo)，完成查找。

4、實(shí)現(xiàn)代碼。

/**

*?description?:?二分查找。

*?@param?array?需要查找的有序數(shù)組

*?@param?from?起始下標(biāo)

*?@param?to?終止下標(biāo)

*?@param?key?需要查找的關(guān)鍵字

*?@return

*/

public?static?E?extends?ComparableE?int?binarySearch(E[]?array,?int?from,?int?to,?E?key)?throws?Exception?{

if?(from??0?||?to??0)?{

throw?new?IllegalArgumentException("params?from??length?must?larger?than?0?.");

}

if?(from?=?to)?{

int?middle?=?(from??1)?+?(to??1);?//?右移即除2

E?temp?=?array[middle];

if?(temp.compareTo(key)??0)?{

to?=?middle?-?1;

}?else?if?(temp.compareTo(key)??0)?{

from?=?middle?+?1;

}?else?{

return?middle;

}

}

return?binarySearch(array,?from,?to,?key);

}

網(wǎng)頁標(biāo)題：java二分查找算法代碼 java二分法查找算法
當(dāng)前URL：http://muchs.cn/article12/doeicgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、軟件開發(fā)、商城網(wǎng)站、動態(tài)網(wǎng)站、服務(wù)器托管、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)