二分查找

查找指定元素

左闭右闭

template<typename T>  
int search1(vector<T> arr, T target) {  
    int left = 0, right = arr.size() - 1;  
    //区间不为空  
    while (left <= right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right+1] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) {  
            return mid;  
        } else if (arr[mid] < target) {  
            left = mid + 1;  
        } else if (arr[mid] > target) {  
            right = mid - 1;  
        }  
    }  
    return -1;  
}

左闭右开

// 左闭右开 [left,right)template<typename T>  
int search2(vector<T> arr, T target) {  
    int left = 0, right = arr.size();  
    //区间不为空  
    while (left < right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) {  
            return mid;  
        } else if (arr[mid] < target) {  
            left = mid + 1;  
        } else if (arr[mid] > target) {  
            right = mid;  
        }  
    }  
    return -1;  
}

左开右开

template<typename T>  
int search3(vector<T> arr, T target) {  
    int left = -1, right = arr.size();  
    //区间不为空  
    while (left + 1 < right) {  
        // 循环不变量：  
        // nums[left] < target  
        // nums[right] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) {  
            return mid;  
        } else if (arr[mid] < target) {  
            left = mid;  
        } else if (arr[mid] > target) {  
            right = mid;  
        }  
    }  
    return -1;  
}

查找大于某个数的首个元素

左闭右闭

/**  
 * 左闭右闭 [left,right] 
 * @tparam T 类型  
 * @param arr 数组  
 * @param target 目标  
 * @return 大于target的第一个下标  
 */template<typename T>  
int lower_bound1(vector<T> arr, T target) {  
    int left = 0, right = arr.size() - 1;  
    //区间不为空  
    while (left <= right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right+1] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid - 1;  
        }  
    }  
    // right+1=left  
    // [0,right] 是红色 [left,size-1] 是蓝色  
    return left; //right+1  
}

左闭右开

/**  
 * 左闭右开 [left,right)
 * @tparam T 类型  
 * @param arr 数组  
 * @param target 目标  
 * @return 大于target的第一个下标  
 */template<typename T>  
int lower_bound2(vector<T> arr, T target) {  
    int left = 0, right = arr.size();  
    //区间不为空  
    while (left < right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid;  
        }  
    }  
    // 此时 left和right都指向结果，但根据红蓝染色法  
    // [0,right) 是红色 [left,size) 是蓝色  
    return right; //left  
}

左开右开

/**  
 * 左开右开 (left,right) * @tparam T 类型  
 * @param arr 数组  
 * @param target 目标  
 * @return 大于target的第一个下标  
 */template<typename T>  
int lower_bound3(vector<T> arr, T target) {  
    int left = -1, right = arr.size();  
    //区间不为空  
    while (left + 1 < right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right] >= target
        int mid = left + (right - left) / 2;  
        if (arr[mid] < target) {  
            left = mid;  
        } else {  
            right = mid;  
        }  
    }  
    //(-1,right) 是红色 (left,size)是蓝色  
    // left+1=right 此刻right指向大于target的第一个数  
    return right; //left+1  
}

附录

#include <bits/stdc++.h>  
using namespace std;  
  
// 左闭右闭 [left,right]template<typename T>  
int search1(vector<T> arr, T target) {  
    int left = 0, right = arr.size() - 1;  
    //区间不为空  
    while (left <= right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right+1] >= target       
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) {  
            return mid;  
        } else if (arr[mid] < target) {  
            left = mid + 1;  
        } else if (arr[mid] > target) {  
            right = mid - 1;  
        }  
    }  
    return -1;  
}  
  
// 左闭右开 [left,right)template<typename T>  
int search2(vector<T> arr, T target) {  
    int left = 0, right = arr.size();  
    //区间不为空  
    while (left < right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) {  
            return mid;  
        } else if (arr[mid] < target) {  
            left = mid + 1;  
        } else if (arr[mid] > target) {  
            right = mid;  
        }  
    }  
    return -1;  
}  
  
// 左开右开 (left,right)template<typename T>  
int search3(vector<T> arr, T target) {  
    int left = -1, right = arr.size();  
    //区间不为空  
    while (left + 1 < right) {  
        // 循环不变量：  
        // nums[left] < target  
        // nums[right] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) {  
            return mid;  
        } else if (arr[mid] < target) {  
            left = mid;  
        } else if (arr[mid] > target) {  
            right = mid;  
        }  
    }  
    return -1;  
}  
  
/**  
 * 左闭右闭 [left,right] * @tparam T 类型  
 * @param arr 数组  
 * @param target 目标  
 * @return 大于target的第一个下标  
 */template<typename T>  
int lower_bound1(vector<T> arr, T target) {  
    int left = 0, right = arr.size() - 1;  
    //区间不为空  
    while (left <= right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right+1] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid - 1;  
        }  
    }  
    // right+1=left  
    // [0,right] 是红色 [left,size-1] 是蓝色  
    return left; //right+1  
}  
  
/**  
 * 左闭右开 [left,right] * @tparam T 类型  
 * @param arr 数组  
 * @param target 目标  
 * @return 大于target的第一个下标  
 */template<typename T>  
int lower_bound2(vector<T> arr, T target) {  
    int left = 0, right = arr.size();  
    //区间不为空  
    while (left < right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid;  
        }  
    }  
    // 此时 left和right都指向结果，但根据红蓝染色法  
    // [0,right) 是红色 [left,size) 是蓝色  
    return right; //left  
}  
  
/**  
 * 左开右开 (left,right) * @tparam T 类型  
 * @param arr 数组  
 * @param target 目标  
 * @return 大于target的第一个下标  
 */template<typename T>  
int lower_bound3(vector<T> arr, T target) {  
    int left = -1, right = arr.size();  
    //区间不为空  
    while (left + 1 < right) {  
        // 循环不变量：  
        // nums[left-1] < target  
        // nums[right] >= target        
        int mid = left + (right - left) / 2;  
        if (arr[mid] < target) {  
            left = mid;  
        } else {  
            right = mid;  
        }  
    }  
    //(-1,right) 是红色 (left,size)是蓝色  
    // left+1=right 此刻right指向大于target的第一个数  
    return right; //left+1  
}  
  
int main() {  
    vector<int> arr{1, 2, 4, 4, 5, 6, 9, 11, 13};  
    cout << "============ binary search ==============" << endl;  
    cout << std::binary_search(arr.begin(), arr.end(), 13) << endl;  
    cout << search1(arr, 13) << endl;  
    cout << search2(arr, 13) << endl;  
    cout << search3(arr, 13) << endl;  
    cout << "==========================" << endl;  
    cout << std::binary_search(arr.begin(), arr.end(), 1) << endl;  
    cout << search1(arr, 1) << endl;  
    cout << search2(arr, 1) << endl;  
    cout << search3(arr, 1) << endl;  
    cout << "==========================" << endl;  
    cout << std::binary_search(arr.begin(), arr.end(), 9) << endl;  
    cout << search1(arr, 9) << endl;  
    cout << search2(arr, 9) << endl;  
    cout << search3(arr, 9) << endl;  
    cout << "==========================" << endl;  
    cout << std::binary_search(arr.begin(), arr.end(), -1) << endl;  
    cout << search1(arr, -1) << endl;  
    cout << search2(arr, -1) << endl;  
    cout << search3(arr, -1) << endl;  
    cout << "==========================" << endl;  
    cout << std::binary_search(arr.begin(), arr.end(), 15) << endl;  
    cout << search1(arr, 15) << endl;  
    cout << search2(arr, 15) << endl;  
    cout << search3(arr, 15) << endl;  
  
    cout << "==========lower bound================" << endl;  
    cout << lower_bound1(arr, 3) << endl;  
    cout << lower_bound2(arr, 3) << endl;  
    cout << lower_bound2(arr, 3) << endl;  
    cout << std::lower_bound(arr.begin(), arr.end(), 3) - arr.begin() << endl;  
}