二分查找

Posted on | Edited on | In | Comments:

概述

二分查找算法是针对有序数组的一个查找，又称为折半查找，时间复杂度为$log_2n$，空间复杂度为$O(1)$

1
2
3
4
5
6
7
8
9
10
int binary_search(vector<int> a, int key) {
    int start = 0, end = a.size()-1, mid = 0;
    while (start<=right) {
        mid = (start+end)>>2;
        if (a[mid] == key)  return mid;     //查找成功返回下标
        else if (key < a[mid])  mid = end-1;
        else    mid = start+1;
    }
    return -1;  //查找失败返回-1
}

示例

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

数组旋转之后，第一个元素是大于等于最后一个元素的（有特殊情况），可用两个指针分别标记第一个跟最后一个元素。可以找到中间元素，如果中间元素大于第一个元素，那么最小元素肯定位于中间元素到最后一个元素之间。则递归后面部分即可。如果中间元素小于最后一个元素，则位于前面部分。最后两个指针相邻，也就是第一个指针指向前面数组部分的最后一个元素，第二个指针指向后面数组部分的第一个元素，即为循环结束条件，第二个指针指向的元素即为最小元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int p = rotateArray.size();
        if (p == 0)     return 0;
        int index1 = 0, index2 = p-1;
        int indexMid = index1;
        while (rotateArray[index1] >= rotateArray[index2]) {
            if (index2-index1 == 1) {
                indexMid = index2;
                break;
            }
            indexMid = (index1+index2)/2;
            //如果三个下标所对应元素值相同则顺序查找
            if (rotateArray[index1] == rotateArray[indexMid] && rotateArray[indexMid] == rotateArray[index2]) {
                int minn = rotateArray[index1];
                for (int i = index1+1; i<=index2; i++) {
                    if (rotateArray[i] < minn)    minn = rotateArray[i];
                }
                return minn;
            }
            if (rotateArray[indexMid] >= rotateArray[index1])     index1 = indexMid;
            else if (rotateArray[indexMid] <= rotateArray[index2]) index2 = indexMid;
        }
        return rotateArray[indexMid];
    }
};