【算法导论】二分查找

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