【算法】二分法

2023-12-17 21:57:05

1、二分法

1.1 二分法原理

? ? ? ? 每次将查找的范围缩小一半,直到最后找到记录或者找不到记录返回。

? ? ? ? 要求:采用二分法查找时,数据需是排好序的。

1.2二分法思路

? ? ? ? 判断某个数是否在数组中存在(例:判断3是否在数组中存在)

? ? ? ?(1)对于排好序的数组,进行第一轮分半,找到第4个位置

? ? ? ? (2) 3比4小,因此向左边查找,进行第二轮分半,找到第2个位置

? ? ? ? (3)3比2大,因此向右边查找,进行第三轮分半,但只有1个位置了,因此直接判断数据是否是3,结束查找。

2、算法分析

2.1逻辑分析

????????由于其对半分的规则,如果所需要的结果刚好在中间位置,则一次获取结果

? ? ? ? 如果其

2.2?时间复杂度

? ? ? ? 由于其操作方法为,每次对半处理,其时间复杂度为

3、code

3.1 java

public static boolean exist(int[] arr, int target) {
        if(arr == null || arr.length == 0){
            return false;
        }
        int left = 0;
        int right = arr.length - 1;
        int mid;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return arr[left] == target;
    }

3.2 python

def exist(arr, target):
    if arr is None or len(arr) == 0:
        return False
    l = 0
    r = len(arr) - 1
    while l < r:
        mid = l + ((r - l) >> 1)
        if arr[mid] == target:
            return True
        elif arr[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return arr[r] == target

文章来源:https://blog.csdn.net/weixin_38996079/article/details/135044285
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。