---
# System prepended metadata

title: 二元搜尋法(Binary Search)

---

# 二元搜尋法(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)`