Num.5

Num.5:

  搜索是OIer们写题时常用的一种手段&＃xff0c;对于每一个题&＃xff0c;他几乎都能骗到一些分&＃xff0c;所以&＃xff0c;掌握了搜索&＃xff0c;成功近在咫尺。

二分搜索

  二分搜索的思想是分而治之。只要理解了这句话&＃xff0c;二分搜索就会了一半&＃xff0c;其实&＃xff0c;二分搜索的主要目的是找到合适的数来解决当前问题。因此&＃xff0c;这二分搜索的效率就特别高了。二分搜索的实现是通过三个关键指针&＃xff0c;即first,middle,last。First指针表示当前搜索范围的第一个元素的编号&＃xff0c;middle指针表示搜索范围中间的数的编号&＃xff0c;last表示搜索范围中最后一个数的编号。一般地&＃xff0c;对于一个有序数列而言&＃xff0c;如果需要元素在搜索范围右边&＃xff0c;那么将first指针转移到middle&＃xff0c;middle继续是中间的&＃xff1b;反之亦然。而当某2个指针重合时&＃xff0c;这个指针所指的元素就是需要元素。