vlambda博客
学习文章列表

二分查找

二分查找又叫做折半查找，其查找过程为：先确定待查记录所在的范围（区间），然后逐步缩小范围知道找到或者找不到该记录为止。注意二分查找是在有序表上进行的，且二分查找也是分治思想的例证。

题目：已知有序数组a= {1, 2, 3, 4, 5,9,11}，查找某个值，若存在，返回数组下标，若不存在，则返回-1。

例如输入：4，返回3

思路：

     * 双指针法  while  low小于等于high时

     * 求出中间坐标 midIndex=(low +high)/2

     * 然后比较目标值与中间坐标的值

     * 如果目标值大 则说明需要查找的值在mid的右侧， low =midIndex+1

     * 如果目标值小 则说明需要查找的值在mid的左侧， high=midIndex-1

     * 如果相等则返回midIndex

时间复杂度O(logn)

空间复杂度O(1)

 public int find(int[] a, int target) {        int low = 0; int high = a.length - 1; while (low <= high) { int midIndex = (low + high) / 2; if (target == a[midIndex]) { return midIndex; } else if (target > a[midIndex]) { low = midIndex + 1; } else if (target < a[midIndex]) { high = midIndex - 1; } } return -1; }

二分查找的应用

LeetCode 704. 二分查找 (Binary Search)

题目描述

统计一个数字在排序数组中出现的次数。

例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3，由于3在这个数组中出现了4次，因此输出4。

示例

示例 1：

输入：[1, 2, 3, 3, 3, 3, 4, 5] ,  3

输出：4 解释：数组中总共有4个3

题解参考：https://mp.weixin.qq.com/s/mOCelQ6nzuGTzb4aFihQBw