一.二分法
简介
二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。
工作原理
以在一个升序数组中查找一个数为例。
它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。
性质
二分查找的最优时间复杂度为 O(1)。
二分查找的平均时间复杂度和最坏时间复杂度均为 O(logn)。因为在二分搜索过程中，算法每次都把查询的区间减半，所以对于一个长度为 n 的数组，至多会进行O(logn) 次查找。
二.题号704 二分查找
题目
思路
问题是标准的二分思想。
1.以有序数列的上下界为初始搜索上下界。
2.取当前搜索上下界的均值作为搜索索引。
3.若搜索索引对应的值大于需要搜索的Target，则收缩搜索上界，将当前索引值作为新的搜索上界，重复2；
若搜索索引对应的值小于需要搜索的Target，则收缩搜索下界，将当前索引值作为新的搜索下界，重复2；
若搜索索引对应的值等于需要搜索的Target，则找到，返回搜索索引值。
4.Case 1:Target不存在于此数组，即搜索上下界重合，此时返回-1。
Case 2:只有两个数的时候，即上界-下界=1，则退出循环，直接看这2个数是否等于Target，没有就返回-1。
Case 3:初始就只有1个数的时候，就一开始没考虑到这一点，导致下标报错！
代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int highbound,lowbound=0;
int index=0;
//Case 3:Only 1 number in given array
if (nums.size()==1)
{
if (nums[0]==target)
return 0;
else
return -1;
}
highbound= nums.size()-1;
//Case1:More than 2 numbers to be scanned
while(highbound-lowbound>1){
index=int((lowbound+highbound)/2);
if (nums[index]==target)
return index;
else {
if (nums[index]>target)
{
highbound=index;
}
else lowbound=index;
}
}
//Case2:Only 2 or less number to be scanned
if (nums[lowbound]==target)
return lowbound;
else if (nums[highbound]==target)
return highbound;
else return -1 ;
}
};
反思
1.我要打死那些百度回答，说C++数组长度只能用sizeof(arr)/sizeof(int)来取，我给试了半个小时都还是报溢出。结果我突然试试arr.size()就解决了。谁能想到在这种细节上挣扎了半个小时， WTF
2.漏考虑了初始数组的极端情况，不仅是查找缩界的时候可能出现只有1个或者2个数的情况，初始的数组也完全有可能出现1个或者2个数。
三.题号278 第一个错误的版本
题目
思路
二分查找的变种问题
相较于标准的二分查找，本题的变更点在于上下界的收缩条件。
原二分查找是根据Target和上下界均值索引所指向元素的大小关系来进行缩界。
本题的缩界条件是：
1.若均值索引所指元素是Good Version,收缩下界为该索引。
2.若均值索引所指元素是Bad Version,收缩上界为该索引。
必须考虑的情况有：
Case 1:初始只有一个版本，那么必为Bad
Case 2:初始只有两个版本，直接判断第一个是否为Bad，如果不是，那第二个一定是Bad
Case 3:正常情况下，Good 和Bad 的边界会逐渐缩进到相邻两个元素，那么此时的搜索上界就是Bad
代码
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
//Case 1: Only 1 version
if (n==1)
return 1;
//Case 3 : More than 2 version
int lowbound=1;
unsigned int highbound=n;
unsigned int index=0;
if (isBadVersion(1))
return 1;
while (lowbound<(highbound-1))
{
index= int((lowbound+highbound)/2);
if (isBadVersion(index)){
highbound=index;
}
else
{
lowbound=index;
}
}
return highbound;
}
};
反思
1.要求是尽可能减少isBadVersion()接口的调用，所以在Case 1 只有一个版本的情况下，这个版本不用调用接口去判断，一定是Bad，直接可以返回1。在Case 2 有2个版本的情况我在实际编码时发现可以归到Case 3中去，那么我就减去了Case 2 单独的判断代码，减少一个时间复杂度O(1)的操作。
2.实际测试中发现给出了非常大数值的样例，导致上下界和Index溢出，解决办法就是使用unsigned int，不过空间有些浪费，所以通过对样例的试探，我将Index和上界改成Unsigned int，下界还是维持int。我觉得在空间复杂度这一点上仍然有优化的空间。
四 题号35 搜索插入位置
思路
1.首先拿到感觉像是一个O（n）的插入操作，但是题目要求用logn的算法来做，那明显就是二分查找的变种
2.如果元素在数组中的话，那就是一个基础的二分查找问题。
3.如果元素不在数组中，那么就与原二分查找问题有些不同。在原问题中，如果搜索的上下界已经紧邻但上下界对应的元素都不等于Target,此时就返回不存在。但在本问题中，这个最终的上下界未必就一定是元素应该插入的位置，因为这个元素可能比最后一个元素都要大，也有可能比第一个元素都要小，这样的话，整个数组就都不在其数值范围之内。所以问题就在于如何确定元素不在数组中，以及确定最后一次查找的搜索上下界。
Case 1：初始数组只有一个元素，如果小于等于Target，则返回0，否则返回1.
Case 2: 初始数组有两个以上的元素，首先考虑第一个元素是否大于Target，或者最后一个元素是否小于Target，如果是，直接返回0或者num.length()就行了。
Case 3 : 初始数组有两个以上的元素，且在数组已有的数值范围内，那么就原计划执行二分查找，返回最后的上界值。
代码
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
unsigned int lowbound=0;
unsigned int index=0;
unsigned int highbound=nums.size()-1;
//case 1 : only 1 number
if (nums.size()==1)
{
if (target>nums[0])
return 1;
else
return 0;
}
//case 2: more than 2 numbers,but bigger or smaller than any numbers in the given array
if (target>nums[highbound])
return nums.size();
if (target<=nums[0])
return 0;
if (target==nums[highbound])
return nums.size()-1;
//case 3: more than 2 numbers, and in the range of the given array
while (highbound>(lowbound+1))
{
index=int((highbound+lowbound)/2);
if (nums[index]==target)
{
return index;
}
if (nums[index]>target)
{
highbound=index;
}
else
{
lowbound=index;
}
}
if (nums[lowbound]==target)
{
return lowbound;
}
else
{
return highbound;
}
}
};
反思
1.途中犯了条件语句的“==”错误，不应该。
2.本来想偷懒，把Target在头和尾的情况都放到Case 2中，但是实际上返回的值不同，Debug了一会儿。
