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;
}