二分查找

二分查找的核心思路

• 二分查找，也叫折半查找。是针对有序数据的一种快速查找算法。
• 二分查找的思想非常简单，就是在区间范围内取中间位置的值进行查找的办法。

二分查找的操作流程

• 假如在一个有序数组中，给我们一个值，去查找这个值在这个数组中的位置。第一步我们取到这个数组的中间位置的值，比如长度位5的a数组，我们直接去a[2]的值（如果数组为偶数个，则取中间数中较小的那个，比如长度为6的数组，我们取a[2]，不取a[3]），直接和要查找的值进行大小比较。如果a[2]大，则可以确定这个数再a[0..1]的区间，则再a[0..2]中继续取中间值和这个数进行比较。如果a[2]小，则再a[3..4]去找中间值取对比。
• 重复上述操作，一直到找到相等的值将下标返回。如果一直找到区间范围只剩一个元素，也不相等，即不存在这个值。

二分查找的相关

• 二分查找的时间复杂度为O(logn)。O(logn)时间复杂度的算法是一类及其高效的算法，有时候甚至比常量级的O(1)时间复杂度算法还要高效。

二分查找的代码简单实现

简单的二分查找并不难写，难写的二分查找的变体问题。以下分别除了简单的二分查找，还变体了4个问题，用代码简单的实现了一下。

- (void)bsearchNumber
{
    NSArray *array = @[@1,@5,@8,@12,@18,@60,@60,@60,@87,@99,@111];
    
    NSLog(@"二分查找 %d ",[self bsearchwithNumber:@60 withArray:array]);
    
    NSLog(@"二分查找递归 %d ",[self bsearchrecursivewithwithNumber:@60 withArray:array withLow:0 withHigh:(int)array.count-1]);
    
    NSLog(@"二分查找第一个等于 %d ",[self bsearchFirstEqualwithNumber:@60 withArray:array]);
    
    NSLog(@"二分查找最后一个等于 %d ",[self bsearchLastEqualwithNumber:@60 withArray:array]);
    
    NSLog(@"二分查找第一个大于等于 %d ",[self bsearchFirstEqualOrGreaterwithNumber:@50 withArray:array]);
    
    NSLog(@"二分查找最后一个小于等于 %d ",[self bsearchLastEqualOrLesswithNumber:@61 withArray:array]);
    
    
}

• 查找等于给定值的元素

- (int)bsearchwithNumber:(NSNumber *)searchNumber withArray:(NSArray *)array
{
    int low = 0;
    int high = (int)array.count-1;
    
    while (low <= high) {
        int mid = low + (high-low)/2;
        if ([array[mid] intValue] == [searchNumber intValue]) {
            return mid;
        }
        if ([array[mid] intValue] > [searchNumber intValue]) {
            high = mid-1;
        }else {
            low = mid+1;
        }
    }
    
    return -1;
}

//二分查找递归形式
- (int)bsearchrecursivewithwithNumber:(NSNumber *)searchNumber withArray:(NSArray *)array withLow:(int)low withHigh:(int)high
{
    if (low > high) {
        return -1;
    }
    
    int mid = low+(high-low)/2;
    
    if ([array[mid] intValue] == [searchNumber intValue]) {
        return mid;
    }else {
        if ([array[mid] intValue] > [searchNumber intValue]) {
            high = mid-1;
        }else {
            low = mid+1;
        }
        return [self bsearchrecursivewithwithNumber:searchNumber withArray:array withLow:low withHigh:high];
    }
}

• 查找第一个值等于给定值的元素

- (int)bsearchFirstEqualwithNumber:(NSNumber *)searchNumber withArray:(NSArray *)array
{
    int low = 0;
    int high = (int)array.count-1;
    
    while (low <= high) {
        int mid = low + (high-low)/2;
        if ([array[mid] intValue] > [searchNumber intValue]) {
            high = mid-1;
        }else if ([array[mid] intValue] < [searchNumber intValue]) {
            low = mid+1;
        }else {
            if (mid == 0 || [array[mid-1] intValue] != [searchNumber intValue]) {
                return mid;
            }else {
                high = mid-1;
            }
        }
    }
    return -1;
    
}

• 查找最后一个值等于给定值的元素

- (int)bsearchLastEqualwithNumber:(NSNumber *)searchNumber withArray:(NSArray *)array
{
    int low = 0;
    int high = (int)array.count-1;
    
    while (low <= high) {
        int mid = low + (high-low)/2;
        
        if ([array[mid] intValue] > [searchNumber intValue]) {
            high = mid-1;
        }else if([array[mid] intValue] < [searchNumber intValue]) {
            low = mid+1;
        }else {
            if (mid == (int)array.count-1 || [array[mid+1] intValue] != [searchNumber intValue]) {
                return mid;
            }else {
                low = mid+1;
            }
        }
    }
    return -1;
    
}

• 查找第一个值大于或等于给定值的元素

- (int)bsearchFirstEqualOrGreaterwithNumber:(NSNumber *)searchNumber withArray:(NSArray *)array
{
    int low = 0;
    int high = (int)array.count-1;
    
    while (low <= high) {
        int mid = low + (high-low)/2;
        if ([array[mid] intValue] >= [searchNumber intValue]) {
            if (mid == 0 || [array[mid-1] intValue] < [searchNumber intValue]) {
                return mid;
            }else {
                high = mid-1;
            }
        }else {
            low = mid+1;
        }
    }
    
    return -1;
}

• 查找最后一个值小于或等于给定值的元素

//二分查找最后一个值小于或等与给定值的元素
- (int)bsearchLastEqualOrLesswithNumber:(NSNumber *)searchNumber withArray:(NSArray *)array
{
    int low = 0;
    int high = (int)array.count-1;
    
    while (low <= high) {
        int mid = low + (high-low)/2;
        if ([array[mid] intValue] <= [searchNumber intValue]) {
            if (mid == (int)array.count-1 || [array[mid+1] intValue] > [searchNumber intValue]) {
                return mid;
            }else {
                low = mid+1;
            }
        }else {
            high = mid-1;
        }
    }
    return -1;
}