# 二元搜尋法(Binary Search)
兩種方式實現：遞迴、非遞迴，下面主要講遞迴的方式實現。
## 舉例說明
請對一個有序數組進行二分搜尋 `{1,8, 10, 89, 1000, 1234}` ，輸入一個數看看該數組是否存在此數，並且求出索引，如果沒有就提示"沒有這個數"。
### 思路
1. 首先確定該陣列的中間索引 `mid = (left + right) /2`
2. 然後讓需要搜尋的數 findVal 和 arr[mid] 比較
2.1 `findVal > arr[mid]` ，說明要搜尋的數在mid右邊，因此需要遞迴的向右搜尋。
2.2 `findVal < arr[mid]` ，說明要搜尋的數在mid左邊，因此需要遞迴的向左搜尋。
2.3 `findVal == arr[mid]`，說明找到，就返回。
**什麼時候結束遞迴?**
1. 找到要搜尋的值。
2. 遞迴完整個陣列，仍然沒有找到findVal，也需要結束遞迴(當left > right就需要退出)。
## 程式碼實現
```java=
package Search;
//注意：使用二元搜尋的前提是該陣列是有序的。
public class BinarySearch {
public static void main(String[] args) {
int arr[] = {1, 8, 10, 89, 1000, 1234};
int index = binarySearch(arr, 0, arr.length - 1, 8);
System.out.printf("搜尋的數索引為: %d\n",index);
int index2 = binarySearch(arr, 0, arr.length - 1, 1000);
System.out.printf("搜尋的數索引為: %d\n",index2);
int index3 = binarySearch(arr, 0, arr.length - 1, 5); // 沒有找到
System.out.printf("搜尋的數索引為: %d\n",index3);
}
/**
*
* @param arr 陣列
* @param left 左邊的索引
* @param right 右邊的索引
* @param findVal 要搜尋的值
* @return 如果找到就返回索引,如果沒找到就返回 -1
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
int mid = (left + right) / 2;
int midVal = arr[mid];
// 當 lfet > right 代表遞迴整個陣列但是沒有找到
if(left > right) {
return -1;
}
if(findVal > midVal) { // 向右遞迴
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
}
```
output
```java=
搜尋的數索引為: 1
搜尋的數索引為: 4
搜尋的數索引為: -1
```
## 陣列中有多個相同數值
如果陣列中有多個相同的數值，那麼搜尋時只會返回第一個找到的索引，例如：
```java=
int arr[] = {1, 8, 10, 89, 1000, 1000, 1000, 1234};
int index = binarySearch(arr, 0, arr.length - 1, 1000);
System.out.printf("搜尋的數索引為: %d\n",index);
```
output
```java=
搜尋的數索引為: 4
```
現在我們需要來完善它，能讓我們找出陣列中所有相同的數。
### 思路分析
1. 在找到 mid 索引值不要馬上返回
2. 向 mid 索引值的左邊遍歷，將所有滿足的元素的索引加入到ArrayList
3. 向 mid 索引值的右邊遍歷，將所有滿足的元素的索引加入到ArrayList
4. 將 ArrayList 返回
首先，我們把方法返回的型態從 int 改為 `ArrayList<Integer>`
```java=
public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findVal) {
//
// code
//
}
```
就像上面思路分析第一點提到的，在找到 mid 索引值不要馬上返回，因此我們要來修正剛剛 else 裡面的內容：
```java=
if(findVal > midVal) { // 向右遞迴
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return binarySearch(arr, left, mid - 1, findVal);
} else {
ArrayList<Integer> resIndexList = new ArrayList<Integer>();
int temp = mid - 1;
while(true) {
if(temp < 0 || arr[temp] != findVal) { // 向左掃到底還是沒找到
break;
}
// 否則,把 temp 放入 resIndexList
resIndexList.add(temp);
temp -= 1;
}
resIndexList.add(mid);
// 向 mid 索引值的右邊掃描, 將所有滿足的元素索引加入到 resIndexList
temp = mid + 1;
while(true) {
if(temp > right || arr[temp] != findVal) { // 向右掃到底還是沒找到
break;
}
// 否則,把 temp 放入 resIndexList
resIndexList.add(temp);
temp += 1;
}
return resIndexList;
}
```
還有搜尋的數找不到原先是返回 `-1` ，現在因為返回型態改為 ArrayList 所以我們改成返回一個空list。
```java=
// 當 lfet > right 代表遞迴整個陣列但是沒有找到
if(left > right) {
return new ArrayList<Integer>(); // 返回空list
}
```
試著跑跑看，在陣列中多加幾筆相同的數值後搜尋：
```java=
public static void main(String[] args) {
int arr[] = {1, 8, 10, 89, 1000, 1000, 1000, 1234};
List<Integer> resIndexList = binarySearch(arr, 0, arr.length - 1, 1000);
System.out.println("1000 在陣列中的索引為: "+resIndexList);
}
```
output
```java=
1000 在陣列中的索引為: [4, 5, 6]
```
### 完整程式碼
```java=
package Search;
import java.util.ArrayList;
import java.util.List;
//注意：使用二元搜尋的前提是該陣列是有序的。
public class BinarySearch {
public static void main(String[] args) {
int arr[] = {1, 8, 10, 89, 1000, 1000, 1000, 1234};
List<Integer> resIndexList = binarySearch(arr, 0, arr.length - 1, 1000);
System.out.println("1000 在陣列中的索引為: "+resIndexList);
}
/**
*
* @param arr 陣列
* @param left 左邊的索引
* @param right 右邊的索引
* @param findVal 要搜尋的值
* @return 如果找到就返回索引,如果沒找到就返回 -1
*/
public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findVal) {
int mid = (left + right) / 2;
int midVal = arr[mid];
// 當 lfet > right 代表遞迴整個陣列但是沒有找到
if(left > right) {
return new ArrayList<Integer>(); // 返回空list
}
if(findVal > midVal) { // 向右遞迴
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return binarySearch(arr, left, mid - 1, findVal);
} else {
ArrayList<Integer> resIndexList = new ArrayList<Integer>();
int temp = mid - 1;
while(true) {
if(temp < 0 || arr[temp] != findVal) { // 向左掃到底還是沒找到
break;
}
// 否則,把 temp 放入 resIndexList
resIndexList.add(temp);
temp -= 1;
}
resIndexList.add(mid);
// 向 mid 索引值的右邊掃描, 將所有滿足的元素索引加入到 resIndexList
temp = mid + 1;
while(true) {
if(temp > right || arr[temp] != findVal) { // 向右掃到底還是沒找到
break;
}
// 否則,把 temp 放入 resIndexList
resIndexList.add(temp);
temp += 1;
}
return resIndexList;
}
}
}
```
## LeetCode - 704. Binary Search
一樣的思路，程式碼如下：
```java=
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid = (left + right) / 2;
while(left <= right) {
if(target < nums[mid]) { // 向左
right = mid - 1;
mid = (left + right) / 2;
} else if (target > nums[mid]) { // 向右
left = mid + 1;
mid = (left + right) / 2;
} else if (target == nums[mid]) {
return mid;
}
}
return -1;
}
}
```
* Runtime: `0 ms`, faster than 100.00% of Java online submissions for Binary Search.
* Memory Usage: `51.7 MB`, less than 7.04% of Java online submissions for Binary Search.
## 時間複雜度
T(n) = T(n/2) + Ο(1) = `Ο(log2n)`
Sign in with Wallet
Connect another wallet