二分法查找
二分法查找原理
使用二分法查找時(shí)需要以下兩個(gè)條件：
沒有重復(fù)元素
已經(jīng)排好順序
假設(shè)給定一組排好序且沒有重復(fù)元素的數(shù)字曾掂，要從這些數(shù)字中快速找到x所在的位置，可以從這組數(shù)字的中間位置開始找俭茧，如果當(dāng)前值與x相等挺物，則查找成功砸彬，如果小于x則從后半段的中間位置繼續(xù)找，如果大于x則從前半段的中間位置繼續(xù)尋找顺囊，直到找到x所在的位置
例如一個(gè)數(shù)組里面的元素有：1,5,8,15,18,23,30
快速找到23對(duì)應(yīng)的下標(biāo)值
第一次：取得數(shù)組的中間位置的值15,15小于23肌索，所以繼續(xù)從后半段開始找，后半段的元素是18,23,30
第二次：取得數(shù)組后半段元素中間位置的值23,23等于23特碳，即找到23對(duì)應(yīng)的下標(biāo)值5
代碼實(shí)現(xiàn)
public class MyArrays{
? ? publicstaticvoidmain(String[] args){
? ? ? ? int[] a = {1,5,8,15,18,23,30};
? ? ? ? int destElement = 23;
? ? ? ? //要求從a數(shù)組中查找23這個(gè)元素的下標(biāo)? ? ? ? int index = binarySearch(a,destElement);
? ? ? ? //如果找到則返回元素的下標(biāo)诚亚，如果找不到統(tǒng)一返回 -1? ? ? ? System.out.println((index==-1)? destElement + "元素不存在！":destElement + "在數(shù)組中的下標(biāo)是：" + index);
? ? }
? ? //二分法查找的核心算法? ? publicstaticintbinarySearch(int[] a,intdestElement){
? ? ? ? int begin = 0;
? ? ? ? int end = a.length-1;
? ? ? ? while(begin <= end){
? ? ? ? ? ? int middle = (begin + end)/2;? ?
? ? ? ? ? ? if(a[middle]==destElement){
? ? ? ? ? ? ? ? return middle;
? ? ? ? ? ? }elseif(a[middle]>destElement){
? ? ? ? ? ? ? ? end = middle - 1;
? ? ? ? ? ? }elseif(a[middle] < destElement){
? ? ? ? ? ? ? ? begin = middle + 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return -1;
? ? }
}
