《iOS面试题整理》 - 二分查找

思路

二分查找必须是一个有序的数据集合, 每次都通过跟区间的中间元素对比, 将查找区间缩小为一半, 直到找到元素或者区间被缩小为 0

时间复杂度

O(logn)

每次查找区间的变化: n, n/2, n/4, n/8 ...... n/2^k

当 n/2^k = 1 时候, k 就是区间缩小的总次数, k = log2 n, 所以时间复杂度O(k) = O(log2 n)

具体实现

1. 普通方法

  int search(int* nums, int numsSize, int target) {
    
    int low = 0;
    int high = numsSize -1;
    
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        
        if(nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

2. 递归实现

  int recursionSearch(int *nums, int low, int high, int target) {
    
    if (low > high) return -1;
    
    int mid = low + ((high - low) >> 1);
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        return recursionSearch(nums, mid + 1, high, target);
    } else {
        return recursionSearch(nums, low, mid - 1, target);
    }
}

int search(int* nums, int numsSize, int target) {
    
    return reverseSearch(nums, 0, numsSize -1, target);
}

leetcode

69. x 的平方根

  int mySqrt(int x) {
    
    if (x <= 1) return x;
    
    int low = 2;
    int high = x / 2;
    
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (mid == x / mid) return mid;
        if (mid < x / mid) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
 
    return low - 1;
}

35 . 搜索插入的位置

  int searchInsert(int* nums, int numsSize, int target) {
    
    if(numsSize == 0) return 0;
    if(nums == NULL) return 0;
    
    int low = 0;
    int high = numsSize -1;
    while (low <=high) {
        
        int mid = low + ((high - low) >> 1);
       
        if (nums[mid] == target) return mid;
        
        if (nums[mid] < target)  {
            low = mid + 1;
        } else {
            high = mid - 1;
        } 
    }
    
    return high + 1;
}

剑指offer 11 题

输入一个递增数组的旋转, 输出旋转数组的最小元素
例如数组 {3,4,5,1,2}, 是 {1,2,3,4,5}的一个旋转, 数组的最小值为1

思路：

• 从头遍历数组, 找出最小的元素, 时间复杂度O(n)
• 最小元素刚好是两个子数组的分界线, 可以用二分查找实现 O(logn)的查找

  - (int)rotateArray:(int *)numbers length:(int)length {
    
    if (numbers == NULL || length <= 0) return -1;
    
    int low = 0;
    int high = length - 1;
    int mid = low;  // 把排序数组前面的0个元素放到后面, 就是数组本身
    while (numbers[low] >= numbers[high]) {
        
        // 如果第一个指针指向第一个递增数组的末尾, 第二个指针指向第二个递增数组的开头
        // 那么 high 就是最小的数字
        if (high - low == 1) {
            mid = high;
            break;
        }
        
        // 有可能开头、结尾、中间的数字都是一样, 没办法区分mid 是属于哪个递增的数组
        if (numbers[low] == numbers[high] && numbers[low] == numbers[mid]) {
            return [self minInOrder:numbers low:low high:high];
        }
        
        mid = low + ((high - low) >> 1);
        if (numbers[mid] >= numbers[low]) {
            low = mid;
        } else if (numbers[mid] <= numbers[high]) {
            high = mid;
        }
    }
    
    return numbers[mid];
}

- (int)minInOrder:(int *)numbers low:(int)low high:(int)high {
    int result = numbers[low];
    for(int i = low + 1; i <= high; i++) {
        if (result > numbers[i]) {
            result = numbers[i];
        }
    }
    return result;
}