【算法】二分法

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