最新消息:

折半查找法(binary search)

算法 大步 420浏览 0评论
前提:
只能对于已经排序的数组使用
折半查找法的核心思想:
1.假设数组为 array,其最小值的下标min,最大值的下标为max。
2.取有序数组取的中间的数,其下标为 mid = (min+max)/2,然后与目标值target比较。
  • 如果刚好target == array[mid],则找到;
  • 如果target >array[mid],则target必然在mid~max之间,此时 min= mid+1;
  • 如果target < array[mid],则target必然在 min~mid之间,此时 max = mid-1;
3.重复第一和第二步,直到max == min。
 
具体描述:

Algorithm:

 

 

 

Below pictures shows the working of algorithm:

Let the array be {6, 13, 14, 25, 33, 43, 51, 53, 64, 72, 84, 93, 95, 96, 96}, and let the data to be searched is 33.

1. Since arr[L] <= data <=arr[H].

binary_search_1

2. Calculate mid, M = (L+H)/2

binary_search_2

3. Since data<arr[M], and all elements on the right of M will be greater than arr[M], hence we can ignore the elements on the right of M and never need to search in arr[M] – arr[H].

binary_search_3

Note: This is not there in linear search. We can never ignore anything in linear search.

4. L and H area adjusted according to the new bounds and M is calculated again.

binary_search_4

5. Since arr[M] < data. the value cannot be present on the left side of M (including M).

binary_search_5

6. Calculating M again, and then checking it against data.

binary_search_6

7. updating L and H again.

binary_search_7

8. Calculating M = (L+H)/2.

binary_search_8

9. arr[M] == data. Hence return M (index where data is found).

a

 
使用时需要考虑的问题:
1.必须是对有序数组使用。所以,当我们先要对数组进行排序,然后查找时,两个操作所花费的时间可能比其他算法大。
2.数组是固定的,要避免溢出。
3.对于折半查找法的实现,分为递归和迭代。递归更占用空间。
非递归的方式(java):
上面这种没有考虑目标值target大于数组最大值或小于数组最大值,所以,为了避免这种情况,我们添加一个判断:
C++实现:
递归的方式(java):
C++实现:

Time Complexity(时间复杂度):

Best Case: O( 1 ) Found at the middle of entire Array
Worst Case: O( lg (n) ) Not found
Average Case: O( lg (n) )

大O计算方法:见非递归的实现,基本操作就是while语句执行的次数,即数组n的规模除以2,知道其值为1,就是说n能除多少次2。公式表示  n/2k=1  ==> k= log2(n)   ,即 lg (n)

 

 

 

Space Complexity(空间复杂度):

Non-Recursive: O(1)
Recursive: O( lg(n) )

非递归的空间复杂度所需要的临时变量是常数个,所以其空间复杂为O(1)
递归的方式,每次都需要计算一次mid,则需要 log2(n)次,所以就是 O( lg(n) )
参考:http://www.ritambhara.in/binary-search-or-half-interval-search/

 

来自为知笔记(Wiz)

 

转载请注明:大步's Blog » 折半查找法(binary search)

SiteMap