//*******二分查找，都注釋了，復(fù)制所有代碼，保存成QuickSortApp.java*************//
創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括彭山網(wǎng)站建設(shè)、彭山網(wǎng)站制作、彭山網(wǎng)頁(yè)制作以及彭山網(wǎng)絡(luò)營(yíng)銷(xiāo)策劃等。多年來(lái)，我們專(zhuān)注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，彭山網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶(hù)以成都為中心已經(jīng)輻射到彭山省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶(hù)的支持與信任！
class ArrayIns
{
private long theArray[];
private int nElems;
//--------------------
public ArrayIns(int max){ //構(gòu)造方法，初始化成員屬性。
theArray = new long[max];
nElems = 0;
}
//-----------------------
public void insert(long value){ //insert方法用于給數(shù)組賦值，并用nElems記錄數(shù)組元素的個(gè)數(shù)。
theArray[nElems] = value;
nElems++;
}
//----------------------------
public void display(){ //display方法用于顯示數(shù)組的所有元素到控制臺(tái)。
System.out.println("A= ");
for(int j=0;jnElems;j++)
System.out.print(theArray[j]+" ");
System.out.println("");
}
//------------------------------
public void quickSort(){ //ArrayIns對(duì)象調(diào)用quickSort方法可以為其成員屬性theArray數(shù)組中的元素排序（從小到大）
recQuickSort(0,nElems-1); //調(diào)用recQuickSort方法開(kāi)始排序，初始范圍從第一個(gè)到最后一個(gè)開(kāi)始。
}
//-------------------------------
private void recQuickSort(int left,int right){ //recQuickSort方法進(jìn)行數(shù)組元素的排序。left,right表示排序的范圍.
if(right-left = 0)
return; //如果right小于left,則第歸返回。此處是第歸的出口。
else {
long pivot = theArray[right]; //每次把排序范圍中的最后一個(gè)數(shù)作為排序時(shí)的參照數(shù)。
int partition = partitionIt(left,right,pivot); //調(diào)用prititionIt方法，參數(shù)列表中指明排序的范圍和參照數(shù)，并將方法的返回值賦給pritition變量(用來(lái)指明下一次排序時(shí)的范圍。)
//System.out.print(" "+1); //數(shù)字1代表第一次第歸的調(diào)用。
recQuickSort(left,partition-1); //第歸調(diào)用本方法，排序右范圍由partition-1來(lái)決定。
//System.out.print(" "+2); //數(shù)字2代表第二次第歸的調(diào)用。
recQuickSort(partition+1,right); //第歸調(diào)用本方法，排序左范圍由partition-1來(lái)決定。
}
}
//-----------------------------------
private int partitionIt(int left,int right,long pivot){ //partitionIt方法完成left和right范圍內(nèi)元素間排序的具體過(guò)程。
int leftPtr = left-1; //leftPrt表示左標(biāo)識(shí)位，從left-1開(kāi)始。
int rightPtr = right; //rightPrt表示右表識(shí)位，到right。 while(true){//永真循環(huán)。
while(theArray[++leftPtr] pivot); // 空循環(huán)，從leftPrt開(kāi)始往rightPrt方向開(kāi)始找一個(gè)比pivot大的數(shù),用leftPtr記錄元素的位置。
while(rightPtr0 theArray[--rightPtr]pivot);//空循環(huán)，從rightPrt往leftPrt方向開(kāi)始找一個(gè)比pivot小的數(shù)，用rightPrt記錄元素的位置,并且rightPtr0會(huì)保證不會(huì)數(shù)組越界。
if(leftPtr = rightPtr) //永真循環(huán)的出口，表示本次排序結(jié)束。
break;//跳出循環(huán)。
else
swap(leftPtr,rightPtr);//將leftPtr和rightPtr所在位置的元素進(jìn)行交換。
}
swap(leftPtr,right); //調(diào)用swap方法。
return leftPtr; //將leftPtr返回到本方法被調(diào)用的位置。用來(lái)指明下一次排序時(shí)的范圍.
}
//---------------------------------------------
private void swap(int dex1,int dex2){ //swap方法用來(lái)將數(shù)組中的兩個(gè)元素進(jìn)行交換，dex1和dex2分別表示兩個(gè)數(shù)組元素的位置。
long temp = theArray[dex1]; //temp變量作為兩個(gè)數(shù)組元素交換時(shí)的臨時(shí)中轉(zhuǎn)變量。
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
}//////////////////////////////////////////////////////////////////////////////////////class QuickSortApp
{
public static void main(String[] args)
{
int maxSize = 10; //定義變量maxSize，并賦初值10.
ArrayIns arr;
arr = new ArrayIns(maxSize);//創(chuàng)建ArrayIns類(lèi)的對(duì)象arr for(int j=0;jmaxSize;j++){
long n = (int)(java.lang.Math.random()*99);//產(chǎn)生隨機(jī)數(shù)。
arr.insert(n); //用insert方法為arr中的成員數(shù)組變量賦值。
}
arr.display(); //用display方法顯示arr中成員變量數(shù)組中的所有元素。
arr.quickSort(); //用quickSort方法為arr成員變量數(shù)組中的元素按從小到大排序。
arr.display(); //顯示。
}
}
圖中這個(gè)時(shí)間是包含在控制臺(tái)輸入的時(shí)間嗎？
結(jié)果是-6的原因是在子串[2,3,4,5,6]中并未找到8這個(gè)數(shù)字。然后我們來(lái)看一下binrySearch的源碼
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)都會(huì)計(jì)算出本輪的中間位置mid，以及獲取中間值midVal。當(dāng)中間值小于key時(shí)，說(shuō)明要找的值在右半邊，low等于mid+1，當(dāng)中間值大于key說(shuō)明在左半邊，high=mid-1,找到了然后開(kāi)始下一輪。當(dāng)?shù)扔跁r(shí)也就是找到了目標(biāo)值，直接返回位置mid。如果最后找不到目標(biāo)值，則返回-(low+1)。
再來(lái)看看具體問(wèn)題的執(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; 此時(shí)low==high跳出while循環(huán) 返回-（5+1）即-6.
拓展知識(shí)
二分查找的流程如下圖：
以下代碼是關(guān)于對(duì)象的 二分查找 的例子，已經(jīng)測(cè)試通過(guò)，執(zhí)行即可。
Student 是基本比較對(duì)象類(lèi)
Dichotomy 是二分法執(zhí)行類(lèi)
Test 是測(cè)試類(lèi)
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 向前移動(dòng), 1 向后移動(dòng), 0 不移動(dòng)
* 這個(gè)方法需要自己進(jìn)行調(diào)整，排序比較和二分查找時(shí)均使用此方法進(jìn)行位置調(diào)整
* 比較時(shí)使用的key自己可以進(jìn)行修改，不過(guò)要保證唯一性，否則查詢(xún)出來(lái)的值會(huì)不準(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();
}
}
1、算法概念。
二分查找算法也稱(chēng)為折半搜索、二分搜索，是一種在有序數(shù)組中查找某一特定元素的搜索算法。請(qǐng)注意這種算法是建立在有序數(shù)組基礎(chǔ)上的。
2、算法思想。
①搜素過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜素過(guò)程結(jié)束；
②如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。
③如果在某一步驟數(shù)組為空，則代表找不到。
這種搜索算法每一次比較都使搜索范圍縮小一半。
3、實(shí)現(xiàn)思路。
①找出位于數(shù)組中間的值，并存放在一個(gè)變量中（為了下面的說(shuō)明，變量暫時(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);
}
二分查找也稱(chēng)折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。
二分查找優(yōu)缺點(diǎn)
優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；
其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。
因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。
使用條件：查找序列是順序結(jié)構(gòu)，有序。
過(guò)程
首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過(guò)程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。
利用循環(huán)的方式實(shí)現(xiàn)二分法查找
public class BinarySearch {
public static void main(String[] args) {
// 生成一個(gè)隨機(jī)數(shù)組 ? ? ? ?int[] array = suiji();
// 對(duì)隨機(jī)數(shù)組排序 ? ? ? ?Arrays.sort(array);
System.out.println("產(chǎn)生的隨機(jī)數(shù)組為： " + Arrays.toString(array));
System.out.println("要進(jìn)行查找的值： ");
Scanner input = new Scanner(System.in);
// 進(jìn)行查找的目標(biāo)值 ? ? ? ?int aim = input.nextInt();
// 使用二分法查找 ? ? ? ?int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);
}
/** ? ? * 生成一個(gè)隨機(jī)數(shù)組 ? ? *
* @return 返回值，返回一個(gè)隨機(jī)數(shù)組 ? ? */
private static int[] suiji() {
// random.nextInt(n)+m ?返回m到m+n-1之間的隨機(jī)數(shù) ? ? ? ?int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環(huán)遍歷為數(shù)組賦值 ? ? ? ?for (int i = 0; i array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** ? ? * 二分法查找 ?---循環(huán)的方式實(shí)現(xiàn) ? ? *
* @param array 要查找的數(shù)組 ? ? * @param aim 要查找的值 ? ? * @return 返回值，成功返回索引，失敗返回-1 ? ? */
private static int binarySearch(int[] array, int aim) {
// 數(shù)組最小索引值 ? ? ? ?int left = 0;
// 數(shù)組最大索引值 ? ? ? ?int right = array.length - 1;
int mid;
while (left = right) {
mid = (left + right) / 2;
// 若查找數(shù)值比中間值小，則以整個(gè)查找范圍的前半部分作為新的查找范圍 ? ? ? ? ? ?if (aim array[mid]) {
right = mid - 1;
// 若查找數(shù)值比中間值大，則以整個(gè)查找范圍的后半部分作為新的查找范圍 ? ? ? ? ? ?} else if (aim array[mid]) {
left = mid + 1;
// 若查找數(shù)據(jù)與中間元素值正好相等，則放回中間元素值的索引 ? ? ?} else {
return mid;
}
}
return -1;
}}
運(yùn)行結(jié)果演示：
由以上運(yùn)行結(jié)果我們得知，如果要查找的數(shù)據(jù)在數(shù)組中存在，則輸出該數(shù)據(jù)在數(shù)組中的索引；如果不存在則輸出 -1 ，也就是打印 -1 則該數(shù)在數(shù)組中不存在，反之則存在。
四、利用遞歸的方式實(shí)現(xiàn)二分法查找
public class BinarySearch2 {
public static void main(String[] args) {
// 生成一個(gè)隨機(jī)數(shù)組 ? ? ? ?int[] array = suiji();
// 對(duì)隨機(jī)數(shù)組排序 ? ? ? ?Arrays.sort(array);
System.out.println("產(chǎn)生的隨機(jī)數(shù)組為： " + Arrays.toString(array));
System.out.println("要進(jìn)行查找的值： ");
Scanner input = new Scanner(System.in);
// 進(jìn)行查找的目標(biāo)值 ? ? ? ?int aim = input.nextInt();
// 使用二分法查找 ? ? ? ?int index = binarySearch(array, aim, 0, array.length - 1);
System.out.println("查找的值的索引位置： " + index);
}
/** ? ? * 生成一個(gè)隨機(jī)數(shù)組 ? ? * ? ? * @return 返回值，返回一個(gè)隨機(jī)數(shù)組 ? ? */
private static int[] suiji() {
// Random.nextInt(n)+m ?返回m到m+n-1之間的隨機(jī)數(shù) ? ? ? ?int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環(huán)遍歷為數(shù)組賦值 ? ? ? ?for (int i = 0; i array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** ? ? * 二分法查找 ---遞歸的方式 ? ? * ? ? * @param array 要查找的數(shù)組 ? ? * @param aim ? 要查找的值 ? ? * @param left ?左邊最小值 ? ? * @param right 右邊最大值 ? ? * @return 返回值，成功返回索引，失敗返回-1 ? ? */
private static int binarySearch(int[] array, int aim, int left, int right) {
if (aim array[left] || aim array[right]) {
return -1;
}
// 找中間值 ? ? ? ?int mid = (left + right) / 2;
if (array[mid] == aim) {
return mid;
} else if (array[mid] aim) {
//如果中間值大于要找的值則從左邊一半繼續(xù)遞歸 ? ? ? ? ? ?return binarySearch(array, aim, left, mid - 1);
} else {
//如果中間值小于要找的值則從右邊一半繼續(xù)遞歸 ? ? ? ? ? ?return binarySearch(array, aim, mid + 1, array.length-1);
}
}}
運(yùn)行結(jié)果演示：
總結(jié)：
遞歸相較于循環(huán)，代碼比較簡(jiǎn)潔，但是時(shí)間和空間消耗比較大，效率低。在實(shí)際的學(xué)習(xí)與工作中，根據(jù)情況選擇使用。通常我們?nèi)绻褂醚h(huán)實(shí)現(xiàn)代碼只要不是太繁瑣都選擇循環(huán)的方式實(shí)現(xiàn)~
重慶分公司
重慶分公司
