本文共 3787 字，大约阅读时间需要 12 分钟。

最近在看算法第四版，其中有说到二分搜索，也就是二分查找，也在leetcode上刷题，总结下：

定义

二分查找又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

优缺点

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。 使用条件：查找序列是顺序结构，有序。

时间复杂度

每次都能将查找区间减半，这种折半特性的算法时间复杂度为 O(logN)。

空间复杂度

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数

非递归方式：

由于辅助空间是常数级别的所以： 空间复杂度是O(1);

递归方式：

递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：

空间复杂度：O(log2N )

实现

1.非递归代码(使用的比较多)

public static int biSearch(int []array,int a){
           int lo=0;        int hi=array.length-1;        int mid;        while(lo<=hi){
               mid=(lo+hi)/2;            if(array[mid]==a){
                   return mid+1;            }else if(array[mid]

2.递归实现

public static int sort(int []array,int a,int lo,int hi){
           if(lo<=hi){
               int mid=(lo+hi)/2;            if(a==array[mid]){
                   return mid+1;            }            else if(a>array[mid]){
                   return sort(array,a,mid+1,hi);            }else{
                   return sort(array,a,lo,mid-1);            }        }        return -1;    }

变种

二分查找可以有很多变种，这里介绍两个变种，实现时要注意边界值和区间的判断。

例如在一个有重复元素的数组中查找 key 的最左位置的实现如下：

• 循环条件为 l < h
• h 的赋值表达式为 h = m
• 最后返回 l 而不是 -1
• 另外，在 h 的赋值表达式为 h = mid 的情况下，如果循环条件为 l <= h，那么会出现循环无法退出的情况，因此循环条件只能是 l < h。

public int binarySearch(int[] nums, int key) {
       int l = 0, h = nums.length - 1;    while (l < h) {
    //注意区间范围        int m = l + (h - l) / 2;        if (nums[m] >= key) {
               h = m;//注意这里h的赋值        } else {
               l = m + 1;        }    }    return l;//最后返回l}

在一个有重复元素的数组中查询元素最后一次出现的位置：

public static int biSearch(int []array,int a){
           int n=array.length;        int low=0;        int hi=n-1;        int mid=0;        while(low

Leetcode题目：

题目描述：

给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 个字符。

Input: letters = [“c”, “f”, “j”] target = “a” Output: “c”

Input:

letters = [“c”, “f”, “j”] target = “c” Output: “f”

Input:

letters = [“c”, “f”, “j”] target = “d” Output: “f”

Input:

letters = [“c”, “f”, “j”] target = “g” Output: “j”

Input:

letters = [“c”, “f”, “j”] target = “j” Output: “c”

Input:

letters = [“c”, “f”, “j”] target = “k” Output: “c”

解题思路：

典型的二分查找的正常实现，最后的时候通过三元运算符判断l跟n大小来决定输出l还是n，在二分查找中，中间值的计算用m = l + (h - l) / 2 比用 m = (l + h) / 2计算要好，可以防止l + h 出现加法溢出。

public char nextGreatestLetter(char[] letters, char target) {
       int n = letters.length;    int l = 0, h = n - 1;    while (l <= h) {
           int m = l + (h - l) / 2;        if (letters[m] <= target) {
               l = m + 1;        } else {
               h = m - 1;        }    }    return l < n ? letters[l] : letters[0];}

题目描述：

给定整数数组，数组按升序排序，找出给定目标值的起始位置和结束位置。

您的算法的运行时复杂性必须是O（log n）的顺序。

如果在数组中找不到目标，则返回[-1，-1]。

Input: nums = [5,7,7,8,8,10], target = 8

Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6

Output: [-1,-1]

解题思路：

本题基于二分查找的变种，考虑先写一个方法来判断target(可重复)在数组中出现的最左位置，再求求target+1出现的最左位置，然后进行比较即可。

class Solution {
       public int[] searchRange(int[] nums, int target) {
           int first = binarySearch(nums,target);        int last = binarySearch(nums,target + 1) -1;		//求target+1出现的最左位置        if(first ==nums.length || nums[first]!=target){
               return new int []{
   -1,-1};        }else{
               return new int[]{
   first,first>last?first:last};	//当查找的目标数在最后一个时,first大于last        }    }    //从数组中找出重复元素的最左位置    private static int binarySearch(int [] nums,int a){
           int l = 0,h = nums.length;	//注意这里h的取值，当数组中为[2,2]目标为2时，first和last都为0，所以这里h不能为nums.length-1;        while(l < h){
               int min = l + (h - l) / 2;            if(nums[min] >= a){
                   h = min;            }else{
                   l = min + 1;            }        }        return l;    }}

转载地址：http://cerwi.baihongyu.com/