算法分析与设计(work3)

问题

在给定的一个集合中找到一个给定的值，并且该集合是已经拍过序的。

解析

1、暴力检索
很容易想到可以从前到后一个一个去查找给定的值，遇到给定的值输出答案即可。
2、二分检索
对于一个有序的数组，那么这个数组就是单调的，已知其单调递增后，就可想到二分检索。每次查找mid下标下的值，如果比给定的值小，那么则将L=mid+1；如果比给定的值大，那么则将R=mid-1；然后求出mid，继续检索，直到找到答案或者L>R为止。

设计

暴力检索伪代码：

For index in range(1,n)
  value[i]==searchnum: output i , break

二分检索伪代码：

While left<=right:
  Mid=(left+right)/2
  value[mid]>searchnum : right=mid-1
  value[mid]<searchnum : left=mid+1
  value[mid]==searchnum : output mid , break

分析

暴力检索：O(n);
二分检索：O(logn);

源码

https://github.com/HaHe-a/Algorithm-analysis-and-design-code/tree/master/Desktop/work3