首页 计算机科学 Java 算法

# 二分查找法

思路： 先将列表中间的元素与要查找的元素比较，如果相等直接返回，如果大了，将中间元素后面的列表元素排除，再在列表开始到列表中间元素之间进行相同操作，直到查找到匹配的元素。

时间复杂度：O (log2 n)

代码：

java:

// 方法一：递归
    public static int binarySearch(int []arr,int target,int low,int high){
        if (arr[low]==target){
            return low;
        }
        if (arr[high]==target){
            return high;
        }
        int mid = (high + low) / 2 ;
        if (arr[mid] == target){
            return mid;
        }
        if (arr[mid] > target){
            return binarySearch(arr,target,low,mid-1);
        }
        if (arr[mid] < target){
            return binarySearch(arr,target,mid + 1,high);
        }
        return -1;
    }
    // 方法二：循环
    public static int binarySearch2(int []arr,int target){
        int low = 0 ;
        int high = arr.length -1 ;
        while (low<=high){
            if (arr[low]==target){
                return low;
            }
            if (arr[high]==target){
                return high;
            }
            int mid = (high + low) / 2 ;
            if (arr[mid] == target){
                return mid;
            }
            if (arr[mid] > target){
                high = mid - 1;
            }
            if (arr[mid] < target){
                low = mid + 1;
            }
        }
        return -1;
    }

python:

# 二分查找中，数组必须是有序的
# 方法一：采用递归的方式
def binary_search(arr:list, target, start, end):
    # 如果 start 索引下的元素就是目标元素，直接返回
    if arr[start] == target:
        return start
    # 如果 end 索引下的元素就是目标元素，直接返回
    if arr[end] == target:
        return end
    # 取中间的元素 为什么是 (end + start) / 2？因为当 start>0 时，中间的索引必须是 (end - start) / 2 + start = (end + start) / 2，必须要加上 start, 否则递归会溢出，无限递归下去。
    mid = int((end + start) / 2)
    # 如果中间的元素是目标元素则直接返回
    if arr[mid] == target:
        return mid
    # 如果中间元素大于目标元素，则递归调用，将 end 设置成中间索引减 1，即 mid - 1
    if arr[mid] > target:
        return binary_search(arr, target, start, mid - 1)
    # 如果中间元素小于目标元素，则递归调用，将 start 设置成中间索引加 1，即 mid+ 1
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, end)
    return None
# 方法二：采用循环的方式
def binary_search_2(arr:list, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        if arr[low] == target:
            return low
        if arr[high] == target:
            return high
        mid = int((low + high) / 2)
        guess = arr[mid]
        if guess == target:
            return mid
        if guess > target:
            low = low + 1
        if guess < target:
            high = high + 1
    return None