精选算法面试 - 数组（二分查找）

李孟

关注

发布于: 2021 年 01 月 13 日

一.简介

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二.示例

2.1 查找元素位置，没有找到返回插入位置

public int searchInsert(int[] nums, int target) {    int left = 0, right = nums.length;    while (left < right)    {        int mid = left + (right - left) / 2;        if (nums[mid] >= target)        {            right = mid;        }        else        {            left = mid + 1;        }    }    return left;}

复制代码

2.2 查找第一个元素

public int binaryByFirst(int[] a,int n,int value){    int lo=0;    int hi=n;    int mid = 0;    while (lo <= hi){        //为了数组越界        mid = lo+((hi-lo)>>1);        if(a[mid] > value){            hi = mid - 1;        }else if(a[mid] < value){            lo=mid+1;        }else{            if((mid == 0) || (a[mid - 1] != value)) return mid;            else hi = mid - 1;        }    }    return -1;}

复制代码

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

public int binaryByFirstBig(int[] a,int n,int value){    int lo=0;    int hi=n;    int mid = 0;    while (lo <= hi){        //为了数组越界        mid = lo+((hi-lo)>>1);        if(a[mid] >= value){            if((mid == 0) || a[mid-1] < value){                return mid;            }else {                hi = mid -1;            }        }else {            lo = mid +1;        }    }    return -1;}

复制代码

2.4 查找最后一个值等于给定值的元素

public int binaryByEnd(int[] a,int n,int value){    int lo=0;    int hi=n;    int mid = 0;    while (lo <= hi){        mid = lo+((hi-lo)>>1);        if(a[mid] > value){            hi = mid - 1;        }else if(a[mid] < value){            lo=mid+1;        }else{            if((mid == n) || (a[mid + 1] != value)) return mid;            else lo = mid + 1;        }    }    return -1;}

复制代码

2.5 查找最后一个小于等于给定值的元素

public int binaryByEndBig(int[] a,int n,int value){int lo = 0;int hi = n;int mid = 0;while (lo <= hi){mid = lo+((hi-lo)>>1);if(a[mid] <= value){if(mid == n || a[mid] > value){return mid;}else{lo = mid+1;}}else {hi = mid -1;}}return -1;}

复制代码

发布于: 2021 年 01 月 13 日阅读数: 21

原文链接:【http://xie.infoq.cn/article/326fa39cab42b3e523941211c】。文章转载请联系作者。

李孟

关注

还未添加个人签名 2017.10.18 加入

数据工程师 https://limeng.blog.csdn.net/

发布

暂无评论

创作场景

精选算法面试 - 数组（二分查找）

一.简介

二.示例

2.1 查找元素位置，没有找到返回插入位置

2.2 查找第一个元素

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

2.4 查找最后一个值等于给定值的元素

2.5 查找最后一个小于等于给定值的元素

李孟

评论