二分法查找原理

使用二分法查找時需要以下兩個條件：

沒有重復元素

已經排好順序

假設給定一組排好序且沒有重復元素的數(shù)字，要從這些數(shù)字中快速找到x所在的位置，可以從這組數(shù)字的中間位置開始找，如果當前值與x相等，則查找成功，如果小于x則從后半段的中間位置繼續(xù)找，如果大于x則從前半段的中間位置繼續(xù)尋找，直到找到x所在的位置

例如一個數(shù)組里面的元素有：1,5,8,15,18,23,30

快速找到23對應的下標值

第一次：取得數(shù)組的中間位置的值15,15小于23，所以繼續(xù)從后半段開始找，后半段的元素是18,23,30

第二次：取得數(shù)組后半段元素中間位置的值23,23等于23，即找到23對應的下標值5

代碼實現(xiàn)

public class MyArrays{

? ? publicstaticvoidmain(String[] args){

? ? ? ? int[] a = {1,5,8,15,18,23,30};

? ? ? ? int destElement = 23;

? ? ? ? //要求從a數(shù)組中查找23這個元素的下標? ? ? ? int index = binarySearch(a,destElement);

? ? ? ? //如果找到則返回元素的下標，如果找不到統(tǒng)一返回 -1? ? ? ? System.out.println((index==-1)? destElement + "元素不存在！":destElement + "在數(shù)組中的下標是：" + 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;

? ? }

}