二分查找 Binary Search

问题

假设有1000万个整数数据，每个数据占8个字节，如何设计数据结构和算法，快速判断某个整数是否在这1000万数据中？如果要求内存尽量节省，不超过100MB，又该怎么做？

二分查找

二分查找是针对一个有序的数据集合，每次拿区间的中位元素值与目标值比较，如果比目标值小，则查找区间移动到中位元素后面，否则，查找区间移动到中位元素前面。如此反复，直到查找到目标值或查找区间为空。

例如需要在0~99的整数区间，查找是否存在23：

性能分析

二分查找的时间复杂度为，其查找效率非常高效，有时甚至比常数级时间复杂度的查找算法还要高效，例如在约42亿()的数据中，使用二分查找的查找次数为32次，而时间复杂度只是一个常数量时间复杂度的表示方式，实际代表的值有可能是，也有可能是。

代码实现

• 递归方式

// search 递归方式实现二分查找
// nums为一个有序数组
// val为需要查找的目标值
// 返回查找到的目标值在数组中的索引，未找到则返回-1
func search(nums []int, val int) int {
    return searchInternally(nums, 0, len(nums)-1, val)
}
func searchInternally(nums []int, lft, rgt, val int) int {
    if lft > rgt {
        return -1
    }
    mid := lft + ((rgt-lft)>>1)
    if nums[mid] == val {
        return mid
    } else if nums[mid] > val {
        return searchInternally(nums, lft, mid-1, val)
    } else {
        return searchInternally(nums, mid+1, rgt, val)
    }
}

• 非递归方式

// search 二分查找 
// nums为一个有序数组
// val为需要查找的目标值
// 返回查找到的目标值在数组中的索引，未找到则返回-1
func search(nums []int, val int) int {
    var lft, rgt = 0, len(nums)-1
    for lft <= rgt {
        mid := (rgt + lft) / 2
        // mid := lft + (rgt-lft)>>1 // 位运算除二
        if nums[mid] == val {
            return mid
        } else if nums[mid] > val {
            rgt = mid - 1
        } else {
            lft = mid + 1
        }
    }
    return -1
}

二分查找的变型

前提条件：原始数据有小到大排列

• 原始数据中有重复数据，查找第一个等于给定值的元素

此时，找到的值与给定元素相等并不表示完结，需要直到找到区间长度为0时才可以结束

var lft, rgt = 0, len(nums) - 1
    for lft <= rgt {
        mid := lft + ((rgt - lft) >> 1)
        if nums[mid] < val {
            lft = mid + 1
        } else if nums[mid] > val {
            rgt = mid - 1
        } else {
            if mid == 0 || nums[mid-1] != val {
                return mid
            } else {
                rgt = mid - 1
            }
        }
    }
    return -1

• 原始数据中有重复数据，查找最后一个等于给定值的元素

var lft, rgt = 0, len(nums) - 1
    for lft <= rgt {
        mid := lft + ((rgt - lft) >> 1)
        if nums[mid] < val {
            lft = mid + 1
        } else if nums[mid] > val {
            rgt = mid - 1
        } else {
            if mid == len(nums)-1 || nums[mid+1] != val {
                return mid
            } else {
                lft = mid + 1
            }
        }
    }
    return -1

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

var lft, rgt = 0, len(nums) - 1
    for lft <= rgt {
        mid := lft + ((rgt - lft) >> 1)
        if nums[mid] < val {
            lft = mid + 1
        } else {
            if mid == 0 || nums[mid-1] < val {
                return mid
            } else {
                rgt = mid - 1
            }
        }
    }
    return -1

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

func bsearch(nums []int, val int) int {
    var lft, rgt = 0, len(nums) - 1
    for lft <= rgt {
        mid := lft + ((rgt - lft) >> 1)
        if nums[mid] > val {
            rgt = mid - 1
        } else {
            if mid == len(nums)-1 || nums[mid+1] > val {
                return mid
            } else {
                lft = mid + 1
            }
        }
    }
    return -1
}

课后题

• 用二分法求一个数的平方根，要求小数点后精度不小于6
• 快速定位IP地址的归属地

将已知IP地址库中对应IP地址转化为32位整数后排序
利用上述查找最后一个小于等于给定值的元素的方法查找