二分查找的核心思路
- 二分查找，也叫折半查找。是针对有序数据的一种快速查找算法。
- 二分查找的思想非常简单，就是在区间范围内取中间位置的值进行查找的办法。
二分查找的操作流程
- 假如在一个有序数组中，给我们一个值，去查找这个值在这个数组中的位置。第一步我们取到这个数组的中间位置的值，比如长度位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;
}
