@markheng 2018-04-12T15:47:00.000000Z 字数 3916 阅读 939

# BinarySearch - 二叉搜索

算法

## Template标准板

int search(vector<int> & nums, int target){    if(nums.size() == 0) return -1;    int lo = 0, hi = nums.size() - 1;    while(lo <= hi)    {        int mid = lo + (hi - lo) / 2;        if(nums[mid] == target) return mid;        else if(target < nums[mid]) hi = mid - 1;        else lo = mid + 1;    }    return -1;}

## 找出下标，不存在则返回-1

- 可认为数组中没有重复元素

class Solution {public:    int search(vector<int>& nums, int target) {        if(nums.size() < 1) return -1;        return binarySearch(nums, 0, nums.size() - 1, target);    }    int binarySearch(vector<int>& nums, int lo, int hi, int target)    {        if(lo >= hi && nums[lo] == target) return lo;        if(lo >= hi && nums[lo] != target) return -1;        //prevent lo + hi overflow        int mid = lo + (hi - lo) / 2;        if(target <= nums[mid]){            return binarySearch(nums, lo, mid, target);        }else{            return binarySearch(nums, mid + 1, hi, target);        }    }};

## 求开方

int mySqrt(int x) {        long long r = x;        while(r * r > x)            r = (r + x / r) / 2;        return r;    }

0 - x（或x/2）是有序的，所以可以利用折半查找的方法

class Solution {public:    int mySqrt(int x) {        if(x == 0) return 0;        int lo = 1, hi = x, ans = 0;        while (lo <= hi)        {            int mid = lo + (hi - lo) / 2;            if (x / mid < mid) //防止溢出            {                hi = mid - 1;            }            else            {                lo = mid + 1;                ans = mid;            }        }        return ans;    }};

## 旋转排序的数组搜索

class Solution {public:    int search(vector<int>& nums, int target) {        int lo = 0, hi = nums.size();        while (lo < hi) {        int mid = (lo + hi) / 2;        double num = (nums[mid] < nums[0]) == (target < nums[0])                   ? nums[mid]                   : target < nums[0] ? -INFINITY : INFINITY;        if (num < target)            lo = mid + 1;        else if (num > target)            hi = mid;        else            return mid;        }        return -1;    }};

## Find First Peek 找到第一个峰

https://leetcode.com/explore/learn/card/binary-search/126/template-ii/948/

if(nums.size() == 0) return -1;if(nums.size() == 1) return 0;if(nums.size() == 2){    if(nums[0] < nums[1]) return 1;    else return 0;}int lo = 0, hi = nums.size() - 1;while(lo < hi){    int mid = lo + (hi - lo) / 2;    if(nums[mid - 1] < nums[mid] &&        nums[mid] < nums[mid + 1])    {        lo = mid + 1;    }else    {        hi = mid;    }}return lo;

## 找到循环有序的序列的最小数

int findMin(vector<int>& nums) {    if(nums.size() == 0) return -1;    if(nums.size() == 1) return nums[0];    int lo = 0, hi = nums.size() - 1;    while(lo + 1 < hi)    {        if(nums[lo] < nums[hi]) return nums[lo];        int mid = lo + (hi - lo) / 2;        if(nums[0] < nums[mid])        {            lo = mid;        }else{            hi = mid;        }    }    if(nums[hi] >= nums[0]) return nums[lo]; // hi 肯定 != 0，不要用lo与0元素比较，否则无法区分[1, 2]和[2, 1]     else return nums[hi];}

## Search for a Range 搜索范围

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,

Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

vector<int> searchRange(vector<int>& nums, int target) {    vector<int> ret(2, -1);    if(nums.size() == 0) return ret;    int lo = 0, hi = nums.size() - 1;    while(lo < hi)    {        int mid = lo + (hi - lo) / 2;        if(target > nums[mid])        {            lo = mid + 1;        }else{            hi = mid;        }    }    if(nums[lo] != target) return ret;    else ret[0] = lo;    hi = nums.size() - 1;    while(lo < hi)    {        int mid = lo + (hi - lo) / 2 + 1; // important        if(target < nums[mid])        {            hi = mid - 1;        }else{            lo = mid;        }    }    ret[1] = hi;    return ret;}

## Find K Closest Elements

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

• The value k is positive and will always be smaller than the length of the sorted array.
• Length of the given array is positive and will not exceed 104
• Absolute value of elements in the array and x will not exceed 104

vector<int> findClosestElements(vector<int>& arr, int k, int x) {    if(x < arr[0]) return vector<int>(arr.begin(), arr.begin()+k);    if(x > arr[arr.size() - 1]) return vector<int>(arr.end() - k, arr.end());    int lo = 0, hi = arr.size() - 1;    while(lo < hi)    {        int mid = lo + (hi - lo) / 2;        if(arr[mid] == x) { hi = mid; break;}        if(arr[mid] < x) lo = mid + 1;        else hi = mid - 1;        }    // hi指向x或者 >= x 的第一个元素    lo = hi;    hi ++;    // 找出k个元素    while(k)    {        if(hi >= arr.size() || lo >= 0 && x - arr[lo] <= arr[hi] - x)        {            lo --;        }else        {            hi ++;        }        k--;    }    //                                 ↓这里要加1    return vector<int>(arr.begin() + lo + 1, arr.begin() + hi);}

• 私有
• 公开
• 删除