查找.md

• 二分查找
  • 1.查找元素第一次出现的下标
  • 2.查找元素最后一次出现的下标

二分查找

int BinarySearch(vector<int> data,int k){
    int sz = data.size();
    int l = 0,r = sz - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(data[mid] > k)
            r = mid - 1;
        else if(data[mid] < k)
            l = mid + 1;
        else
            return mid;
    }
    
    return -1;
}

1.查找元素第一次出现的下标

int GetFirstK(vector<int> data,int k){
    int sz = data.size();
    int l = 0,r = sz - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(data[mid] > k)
            r = mid - 1;
        else if(data[mid] < k)
            l = mid + 1;
        else{
            if(mid == 0 || data[mid - 1] != k) 
                return mid;
            else 
                r = mid - 1;
        }
    }
    
    return -1;
}

2.查找元素最后一次出现的下标

int GetLastK(vector<int> data,int k){
    int sz = data.size();
    int l = 0,r = sz - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(data[mid] > k)
            r = mid - 1;
        else if(data[mid] < k)
            l = mid + 1;
        else{
            if(mid == sz - 1 || data[mid + 1] != k)
                return mid;
            else
                l = mid + 1;
        }
    }
    
    return -1;
}

相关题目:

• 剑指offer(11)：旋转数组的最小数字
• Leetcode(33)：旋转后数组中查找数字
• 剑指offer(53)：数字在排序数组中出现的次数
• 剑指offer(53)：0~n-1中缺失的数字
• 剑指offer(53)：数组中数值和下标相等的元素