1、二分法

1.1 二分法原理

? ? ? ? 每次將查找的范圍縮小一半，直到最后找到記錄或者找不到記錄返回。

? ? ? ? 要求：采用二分法查找時(shí)，數(shù)據(jù)需是排好序的。

1.2二分法思路

? ? ? ? 判斷某個(gè)數(shù)是否在數(shù)組中存在（例：判斷3是否在數(shù)組中存在）

? ? ? ?(1)對(duì)于排好序的數(shù)組，進(jìn)行第一輪分半，找到第4個(gè)位置

? ? ? ? (2) 3比4小，因此向左邊查找，進(jìn)行第二輪分半，找到第2個(gè)位置

? ? ? ? (3)3比2大，因此向右邊查找，進(jìn)行第三輪分半，但只有1個(gè)位置了，因此直接判斷數(shù)據(jù)是否是3，結(jié)束查找。

2、算法分析

2.1邏輯分析

????????由于其對(duì)半分的規(guī)則，如果所需要的結(jié)果剛好在中間位置，則一次獲取結(jié)果

? ? ? ? 如果其

2.2?時(shí)間復(fù)雜度

? ? ? ? 由于其操作方法為，每次對(duì)半處理，其時(shí)間復(fù)雜度為

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