文章目錄
- 前言
- 一、二分查找是什么？
- 二、原理分析
- 三、程序演示
- 四、代碼實作
- 總結
前言
這幾天覺得這些基礎演算法還是很有意思的，所以就繼續“玩”了一下，又發現一個有趣的東西，建立排好序的集合基礎上進行的演算法——二分查找，這不剛剛弄懂了一點排序，就迫不及待的學起來了！！！
一、二分查找是什么？
二分查找是一種快速檢索資料的演算法，又稱折半查找，
使用二分查找是需要前提的，被查找集合是有序的否則無法查找，查找到以后回傳被查找數的索引（下標），
二、原理分析
二分查找演算法其實就是每次都查找中間那個數，如果排序是升序排列，將需要查找的數與中間數比較，如果是小于，那么這個數就在前半部分，如果是大于則就在后半部中去查找，如果排序是降序排列，則反之，按照這個規律依次查找，直到找到最后一個中間數，當然如果該集合中有這個數的話則回傳下標，集合中么有這個數則回傳-1；
三、程序演示
為了方便演示，直接建立一個有序int型別陣列{3,4,5,6,7,8}
查找元素4所在的位置
因為判斷次數是未知的所以用while回圈更方便
初始陣列
| 索引 | minIndex = 0 | 1 | midindex = 2 | 3 | 4 | maxIndex = 5 |
|---|---|---|---|---|---|---|
| 元素 | 3 | 4 | 5 | 6 | 7 | 8 |
經過第一次判斷賦值后
| 索引 | minIndex=midIndex = 0 | maxIndex =1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 元素 | 3 | 4 | 5 | 6 | 7 | 8 |
經過第二次判賦值制后
| 索引 0 | minIndex =maxIndex=midIndex =1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 元素 | 3 | 4 | 5 | 6 | 7 | 8 |
這樣array[midindex] = 4 就是我們要找的數，回傳4所在的下標，
四、代碼實作
代碼如下（示例）：
public class Test03 {
public static void main(String[] args) {
int[] array = {3,4,5,6,7,8}; // 創建一個int型別的陣列
int index = binarySearch(array, 4);// 呼叫binarySearch方法傳入需要的引數，且接受回傳值
System.out.println(index);
}
public static int binarySearch(int[] array,int value) {//創建binarySearch方法帶兩個引數，一個是int陣列，一個是整數，且有int回傳值
int maxIndex = array.length-1; //根據陣列元素設定最大下標
int minIndex =0;//設定最小下標
int midIndex = (maxIndex+minIndex)/2;//根據最大和最小下標得出中間下標（注意：int型別的除法是向下取整）
while(array[midIndex]!=value) {//判斷中間下標對應的值是否是需要查找的值
if(maxIndex>=minIndex) {// 加強判斷，正常情況下minIndex是不能大于maxIndex，加強代碼的健壯性
if(array[midIndex]>value) {//判斷如果中間下標對應的值大于需要查找的值，則更改最大下標為midIndex-1
maxIndex = midIndex-1;
}else if(array[midIndex]<value) {//判斷如果中間下標對應的值小于需要查找的值，則更改最大下標為midIndex+1
minIndex = midIndex+1;
}
midIndex = (maxIndex+minIndex)/2;//從新賦值給中間下標（midIndex）
}else {
midIndex = -1; // 如果輸入的值在被查找的集合中不存在，則回傳-1提醒
break; //退出整個行程
}
}
return midIndex;
}
}
代碼如下（輸出）：
1
總結
其實對于這些基礎演算法個人覺得懂原理比較重要，因為原理只有一個但是實作方式多種多樣，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/254064.html
標籤：java