【算法】二分法

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 Falsel = 0r = len(arr) - 1while l < r:mid = l + ((r - l) >> 1)if arr[mid] == target:return Trueelif arr[mid] > target:r = mid - 1else:l = mid + 1return arr[r] == target