# 二分搜索 > 原文： [https://www.programiz.com/dsa/binary-search](https://www.programiz.com/dsa/binary-search) #### 在本教程中，您將學習二分搜索排序的工作方式。 此外，您還將找到 C，C++ ，Java 和 Python 中的二分搜索的工作示例。 二分搜索是一種搜索算法，用于在排序數組中查找元素的位置。 在這種方法中，總是在數組的一部分中間搜索元素。 二分搜索只能在項目的排序列表上實現。 如果元素尚未排序，則需要首先對其進行排序。 * * * ## 二分搜索原理 二分搜索算法可以通過以下兩種方式實現。 1. 迭代方法 2. 遞歸方法 遞歸方法遵循[分治](/dsa/divide-and-conquer)方法。 這兩種方法的一般步驟將在下面討論。 1. 將在其中執行搜索的數組為：  初始數組 令`x = 4`為要搜索的元素。 2. 將兩個指針分別在最低和最高位置設置為低和高。  設置指針 3. 找到數組中間的中間元素，即`(arr[low + high]) / 2 = 6`。  中間元素 4. 如果`x == mid`，則返回`mid`，否則將要搜索的元素與`m`進行比較。 5. 如果為`x > mid`，則將`x`與中間元素的右側元素進行比較。 這是通過將`low`設置為`low = mid + 1`來實現的。 6. 否則，將`x`與中間元素的左側元素進行比較。 這可以通過將`high`設置為`high = mid - 1`來完成。  尋找中間元素 7. 重復步驟 3 到 6，直到低點遇到高點為止。  中間元素 8. 找到`x = 4`。  * * * ## 二分搜索算法 ### 迭代方法 ``` do until the pointers low and high meet each other. mid = (low + high)/2 if (x == arr[mid]) return mid else if (x > A[mid]) // x is on the right side low = mid + 1 else // x is on the left side high = mid - 1 ``` ### 遞歸方法 ``` binarySearch(arr, x, low, high) if low > high return False else mid = (low + high) / 2 if x == arr[mid] return mid else if x < data[mid] // x is on the right side return binarySearch(arr, x, mid + 1, high) else // x is on the right side return binarySearch(arr, x, low, mid - 1) ``` * * * ## Python，Java，C/C++ 示例（迭代方法） ```py # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array[mid] == x: return mid elif array[mid] < x: low = mid + 1 else: high = mid - 1 return -1 array = [3, 4, 5, 6, 7, 8, 9] x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found") ``` ```java // Binary Search in Java class BinarySearch { int binarySearch(int array[], int x, int low, int high) { // Repeat until the pointers low and high meet each other while (low <= high) { int mid = low + (high - low) / 2; if (array[mid] == x) return mid; if (array[mid] < x) low = mid + 1; else high = mid - 1; } return -1; } public static void main(String args[]) { BinarySearch ob = new BinarySearch(); int array[] = { 3, 4, 5, 6, 7, 8, 9 }; int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); } } ``` ```c // Binary Search in C #include <stdio.h> int binarySearch(int array[], int x, int low, int high) { // Repeat until the pointers low and high meet each other while (low <= high) { int mid = low + (high - low) / 2; if (array[mid] == x) return mid; if (array[mid] < x) low = mid + 1; else high = mid - 1; } return -1; } int main(void) { int array[] = {3, 4, 5, 6, 7, 8, 9}; int n = sizeof(array) / sizeof(array[0]); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; } ``` ```cpp // Binary Search in C++ #include <iostream> using namespace std; int binarySearch(int array[], int x, int low, int high) { // Repeat until the pointers low and high meet each other while (low <= high) { int mid = low + (high - low) / 2; if (array[mid] == x) return mid; if (array[mid] < x) low = mid + 1; else high = mid - 1; } return -1; } int main(void) { int array[] = {3, 4, 5, 6, 7, 8, 9}; int x = 4; int n = sizeof(array) / sizeof(array[0]); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); } ``` * * * ## Python，Java，C/C++ 示例（遞歸方法） ```py # Binary Search in python def binarySearch(array, x, low, high): if high >= low: mid = low + (high - low)//2 # If found at mid, then return it if array[mid] == x: return mid # Search the left half elif array[mid] > x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = [3, 4, 5, 6, 7, 8, 9] x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found") ``` ```java // Binary Search in Java class BinarySearch { int binarySearch(int array[], int x, int low, int high) { if (high >= low) { int mid = low + (high - low) / 2; // If found at mid, then return it if (array[mid] == x) return mid; // Search the left half if (array[mid] > x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); } return -1; } public static void main(String args[]) { BinarySearch ob = new BinarySearch(); int array[] = { 3, 4, 5, 6, 7, 8, 9 }; int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); } } ``` ```c // Binary Search in C #include <stdio.h> int binarySearch(int array[], int x, int low, int high) { if (high >= low) { int mid = low + (high - low) / 2; // If found at mid, then return it if (array[mid] == x) return mid; // Search the left half if (array[mid] > x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); } return -1; } int main(void) { int array[] = {3, 4, 5, 6, 7, 8, 9}; int n = sizeof(array) / sizeof(array[0]); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); } ``` ```cpp // Binary Search in C++ #include <iostream> using namespace std; int binarySearch(int array[], int x, int low, int high) { if (high >= low) { int mid = low + (high - low) / 2; // If found at mid, then return it if (array[mid] == x) return mid; // Search the left half if (array[mid] > x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); } return -1; } int main(void) { int array[] = {3, 4, 5, 6, 7, 8, 9}; int x = 4; int n = sizeof(array) / sizeof(array[0]); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); } ``` * * * ## 二元搜索的復雜度 **時間復雜度** * **最佳情況復雜度**：`O(1)` * **平均情況復雜度**：`O(log n)` * **最壞情況的復雜度**：`O(log n)` **空間復雜度** 二分查找的空間復雜度為`O(n)`。 * * * ## 二分搜索應用 * 在 Java，.Net，C++ STL 庫中 * 在調試時，二分搜索用于查明錯誤發生的位置。