1. 描述（查找算法）：
输入：n个数的一个序列 A = （a1, a2, a3,.....an）和一个值v
输出：下表 i 使得 v=A[i] 或者 v 不在A中出现时，输出 NIL
二分查找的前提是A必须是有序序列， 以下全部假设是A是非降序序列
2. 图解
3. 伪代码
//用递归 BINARY_SEARCH(A, v, low, high) if(low <= high) mid = (low+high)/2 //向下取整 if v == A[mid] return mid; else if v < A[mid] return BINARY_SEARCH(A, v, low, mid-1) else if v > A[mid] return BINARY_SEARCH(A, v, mid+1, high) return NIL //用循环 BINARY_SEARCH(A, v) low = 1 high = A.length while low <= high mid = (low + high)/2 //向下取整 if v == A[mid] return mid else if v < A[mid] high = mid -1 else if v > A[mid] low = mid +1
return NIL
4. 代码实现
java
//用循环 int binarySearch1(int[] A, int v){ int low = 0; int high = A.length; while (low <= high) { int mid = (low + high)/2; if (v == A[mid]) return mid; else if (v < A[mid]) high = mid - 1; else if (v > A[mid]) low = mid + 1; return -1; } //用递归 int binarySearch2(int[] A, int v, int low, int high) { if (low <= high) { int mid = (low + high)/2; if (v == A[mid]) return mid; else if (v < A[mid]) return binarySearch2(A, v, low, mid - 1); else if (v > A[mid]) return binarySearch2(A, v, mid + 1, high); return -1; }
python
# 用循环 def binary_search1(nums, v): low = 0 high = len(nums) while low <= high: mid = int((low + high) / 2) if v == nums[mid]: return mid else: if v <= nums[mid]: high = mid - 1 else: if v > nums[mid]: low = mid + 1 return -1 # 用递归 def binary_search2(nums, v, low, high): if low <= high: mid = int((low + high) / 2) if v == nums[mid]: return mid else: if v < nums[mid]: return binary_search2(nums, v, low, mid - 1) else: if v > nums[mid]: return binary_search2(nums, v, mid + 1, high) return -1
C语言
//用循环 int binary_search1(int arr[], int v, int len) { int low, mid, high; low = 0, high = len-1; while (low <= high) { mid = (low + high) / 2; if (v == arr[mid]) return v; else if (v > arr[mid]) low = mid + 1; else if (v < arr[mid]) high = mid -1; } return -1; } //用递归 int binary_search2(int arr[], int v, int low, int high) { int mid; if (low <= high) { mid = (low + high) / 2; if (v == arr[mid]) return v; else if (v > arr[mid]) return binary_search2(arr, v, mid + 1, high); else if (v < arr[mid]) return binary_search2(arr, v, low, mid - 1); } return -1; }
