给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路分析:

采用二分查找的数组模板,条件设定为val>=x,找到了绿色边界,然后判断绿色边界是否为数组长度.如果是,说明全是红色元素,所以没有找到可行解,返回-1,否则判断绿色边界对应的值是否是给定的x,如果不是,则返回-1,说明没有满足条件的解.最后,一定能够找到满足条件的解,直接返回即可.

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(int val, int x);int binarySearch(int *arr, int arrSize, int x) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/int isGreen(int val, int x) {    return val >= x;                       // (1)条件是数组的值>=X}int search(int* nums, int n, int target){    int r = binarySearch(nums, n, target); // (2)找到绿色边界    if(r == n || nums[r] != target)        // (3)找到绿色边界,然后判断绿色边界是否为数组长度,如果是,说明全      //部是红色元素,所以没有找到可行解,返回-1,否则判断绿色边界对应的值是否是给定的x,如果不是,则返回-1              return -1;    return r;                              // (4)满足条件返回}

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。

思路分析:

采用二分查找的数组模板,先枚举一个数x,然后对于它后面的数组中采用枚举找到

target-x,如果能找到则直接返回一组解即可.

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(int val, int x);int binarySearch(int *arr, int arrSize, int x) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/int isGreen(int val, int x) {    return val >= x;}int search(int* nums, int n, int target){    int r = binarySearch(nums, n, target);    if(r == n || nums[r] != target)        return -1;    return r;}int* twoSum(int* nums, int numsSize, int target, int* returnSize){    int i, pos, base;    int *ret = (int *)malloc( sizeof(int) * 2 );  // (1)申请一个返回数据的数组    *returnSize = 0;                              // (2)初始化返回数组长度为0,有可能找不到解    for(i = 0; i < numsSize; ++i) {                       base = i+1;                               // (3)小的那个数是nums[i],则从i+1这个位置开始往后找        pos = search(nums+base , numsSize-base, target - nums[i]);             if(pos != -1) {                           // (4)不等于-1表示精确找到这个数,直接返回.            ret[0] = i + 1;            ret[1] = pos+base + 1;            *returnSize = 2;            return ret;        }    }    return ret;}

给定一个整数数组 nums 和一个整数目标值 target，请在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

思路分析:

首先,我们可以对数组进行排序,然后枚举一个数,二分枚举另一个数,从而找到一个可行解.

但是问题在于,要求输出的是下标,排序以后下标就乱了.

所以可以引入一个结构体,结构体存储的是值和下标两个值,并且实现一个仿函数,对值进行排序.然后再进行枚举和二分枚举,如果找到可行解,就将结构体的成员变量中的下标塞到结果数组中.

class Solution {    class Point {                                       // (1)结构体存储的是给定数组的值和下标        int val, idx;    public:        Point(){}        Point(int _v, int _i): val(_v), idx(_i) {}        int getval() const {            return val;        }        int getidx() const {            return idx;        }        bool operator < (const Point& o) const {            return val < o.val;        }    };public:    int find(vector<Point>& numbers, int indexStart, int target) {  // (2)二分查找函数,查找的是从数组      //的下标开始到结尾中存在的target所在的下标,不存在就返回-1;        int l = indexStart;        int r = numbers.size() - 1;        while(l <= r) {            int mid = (l + r) >> 1;            if(target == numbers[mid].getval()) {                return mid;            }else if(target > numbers[mid].getval()) {                l = mid + 1;            }else {                r = mid - 1;            }        }        return -1;    }    vector<int> twoSum(vector<int>& nums, int target) {        vector <int> ans;        vector< Point > pts;        for(int i = 0; i < nums.size(); ++i) {            pts.push_back( Point(nums[i], i) );        }        sort(pts.begin(), pts.end());                               // (3)组织原本的整形数组的数据结构到结构体数组中        for(int i = 0; i < pts.size(); ++i) {                       // (4)枚举数组的每个位置,数组有序后,二分查找            int idx = find(pts, i+1, target - pts[i].getval());            if(idx != -1) {                                         // (5)如果x!=-1,那么i和x,就是满足题意的目标                ans.push_back(pts[i].getidx());                ans.push_back(pts[idx].getidx());                return ans;            }        }        return ans;    }};

给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。

思路分析:

先排序使其有序,然后枚举一个数,在左边找没有它的两倍,在右边二分找有没有它的二倍.

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(int val, int x);int binarySearch(int *arr, int arrSize, int x) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/int isGreen(int val, int x) {    return val >= x;}int search(int* nums, int n, int target){    int r = binarySearch(nums, n, target);    if(r == n || nums[r] != target)        return -1;    return r;}int cmp(const void *a, const void *b) {    return *( (int *)a ) - * ( (int*)b );}bool checkIfExist(int* arr, int arrSize){    qsort(arr, arrSize, sizeof(int), cmp);                  // (1)排序    int i, pos, base;     for(i = 0; i < arrSize; ++i) {                       base = i+1;        pos = search(arr+base , arrSize-base, 2*arr[i]);    // (2)右边找两倍的数,找到返回        if(pos != -1) {            return true;        }        pos = search(arr , i, 2*arr[i]);                    // (3)有可能有负数,所以左边也要找,找到返回        if(pos != -1) {            return true;        }    }    return false;}

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

思路分析:

划分数组,比给定字母大的作为绿色,否则为红色.找到绿色的最左边界,如果最左边界为n,

代表所有字符都比他小,则返回第一个字符.

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(char val, char x);int binarySearch(char *arr, int arrSize, char x) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/int isGreen(char val, char x) {    return val > x;}char nextGreatestLetter(char* letters, int lettersSize, char target){    int pos = binarySearch(letters, lettersSize, target);    if(pos == lettersSize) {        return letters[0];    }    return letters[pos];}

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

思路分析:

划分数组,>=target的数为绿色,剩下的为红色,二分找到绿色边界,如果绿色边界不等于n,且对应位置的值等于target,则继续找>=target+1的满足条件的红色边界,返回两个边界就是答案,否则,返回[-1,1].

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(int val, int x);int binarySearch(int *arr, int arrSize, int x) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/int isGreen(int val, int x) {    return val >= x;}int* searchRange(int* nums, int numsSize, int target, int* returnSize){    int l, r;    int *ret = (int *)malloc( sizeof(int) * 2 );    *returnSize = 2;    l = binarySearch(nums, numsSize, target);       // (1)    if(l == numsSize || nums[l] != target) {        // (2)        ret[0] = ret[1] = -1;        return ret;    }    r = binarySearch(nums, numsSize, target+1) - 1; // (3)    ret[0] = l;    ret[1] = r;    return ret;}

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

/************** 二分查找 数组 模板 **************//*  1）传参的数组满足：红红红红红红红红绿绿绿绿绿绿绿；   2）返回值：绿色区段的左边界； */int isGreen(int val, int x);int binarySearch(int *arr, int arrSize, int x) {    int l = -1, r = arrSize;    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(arr[mid], x) )            r = mid;        else            l = mid;    }    return r;}/************** 二分查找 数组 模板 **************/int isGreen(int val, int x) {    return val >= x;}int searchInsert(int* nums, int numsSize, int target){    return binarySearch(nums, numsSize, target);     // (1)分目标值存在和不存在考虑问题}

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

#define ll long long/**************二分查找模板 返回绿色边界**************/int isGreen(int val, int x);int binarySearch(int l, int r, int x) {    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(mid, x) )            r = mid;        else            l = mid;    }    return r;}/**************二分查找模板 返回绿色边界**************/int isGreen(int val, int x) {    return (ll)val * val > x;}int mySqrt(int x){    int r;    if(x == 0 || x == 1) {        return x;    }    r = binarySearch(0, x, x);   // (1)    return r - 1;                // (2)}

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

思路分析:

这个函数时单调递增函数,找到f(k)<=x;且尽量大

x=0,x=1时,直接返回x;x>1构造红色边界f(k)<=x;的情况就是红色,反之为绿色.

#define ll long long/**************二分查找模板 返回绿色边界**************/int isGreen(int val, int x);int binarySearch(int l, int r, int x) {    int mid;    while(l + 1 < r) {        mid = l + (r - l) / 2;        if( isGreen(mid, x) )            r = mid;        else            l = mid;    }    return r;}/**************二分查找模板 返回绿色边界**************/int isGreen(int val, int x) {    return (ll)val * val > x;}int mySqrt(int x){    int r;    if(x == 0 || x == 1) {        return x;    }    r = binarySearch(0, x, x);   // (1)找到绿色边界    return r - 1;                // (2)返回红色边界}