思路
二分查找必须是一个有序的数据集合, 每次都通过跟区间的中间元素对比, 将查找区间缩小为一半, 直到找到元素或者区间被缩小为 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;
}
