二分查找的核心思路

• 二分查找，也叫折半查找。是針對有序數據的一種快速查找算法。
• 二分查找的思想非常簡單，就是在區(qū)間范圍內取中間位置的值進行查找的辦法。

二分查找的操作流程

• 假如在一個有序數組中，給我們一個值，去查找這個值在這個數組中的位置。第一步我們取到這個數組的中間位置的值，比如長度位5的a數組，我們直接去a[2]的值（如果數組為偶數個，則取中間數中較小的那個，比如長度為6的數組，我們取a[2]，不取a[3]），直接和要查找的值進行大小比較。如果a[2]大，則可以確定這個數再a[0..1]的區(qū)間，則再a[0..2]中繼續(xù)取中間值和這個數進行比較。如果a[2]小，則再a[3..4]去找中間值取對比。
• 重復上述操作，一直到找到相等的值將下標返回。如果一直找到區(qū)間范圍只剩一個元素，也不相等，即不存在這個值。

二分查找的相關

• 二分查找的時間復雜度為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;
}