[经典面试题]二分查找问题汇总

[算法]二分查找算法

1.【给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1。】

【题目】

给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1。

【分析】

此题也就是求target在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找，如果不存在直接返回-1，

如果存在，然后再顺序找到这个等于target值区间的最左位置，这样的话，最坏情况下的复杂度就是O（n）了，没有完全发挥出二分查找的优势。

这里的解法具体过程请参考实现代码与注释。

【代码】
/*********************************
*   日期：2015-01-05
*   作者：SJF0115
*   题目: 给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1
*   博客：
**********************************/
#include <iostream>
using namespace std;

int BinarySearch(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start < end){
        int mid = (start + end) / 2;
        if(A[mid] < target){
            start = mid + 1;
        }//if
        else{
            end = mid;
        }//else
    }//while
    // 目标不存在的情况
    // 此时start = end
    if(A[start] != target){
        return -1;
    }//if
    else{
        return start;
    }
}

int main(){
    int A[] = {2,3,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearch(A,11,4)<<endl;
    return 0;
}
/*********************************
*   日期：2015-01-05
*   作者：SJF0115
*   题目: 给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1
*   博客：
**********************************/
#include <iostream>
using namespace std;

int BinarySearchMin(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素左边元素等于目标元素
            if(mid - 1 >= 0 && A[mid - 1] == target){
                end = mid - 1;
            }//if
            else{
                return mid;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}

int main(){
    int A[] = {4,4,4,4,4,5,6,7,8};
    cout<<BinarySearchMin(A,11,4)<<endl;
    return 0;
}

2.【给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1】

【题目】

给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1

【分析】

和上题类似

【代码】
/*********************************
*   日期：2015-01-05
*   作者：SJF0115
*   题目: 给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1
*   博客：
**********************************/
#include <iostream>
using namespace std;

int BinarySearchMax(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素右边元素等于目标元素
            if(mid + 1 < n && A[mid + 1] == target){
                start = mid + 1;
            }//if
            else{
                return mid;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}

int main(){
    int A[] = {2,3,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearchMax(A,11,4)<<endl;
    return 0;
}

3.【给定一个有序（非降序）数组A，可含有重复元素，小于target的最大元素的位置，不存在则返回-1】

【题目】

给定一个有序（非降序）数组A，可含有重复元素，小于target的最大元素的位置，不存在则返回-1

【分析】

这个问题可以转换为给定一个有序（非降序）数组A，可含有重复元素，等于target的最小元素的前一个，不存在则返回-1

【代码】
/*********************************
*   日期：2015-01-05
*   作者：SJF0115
*   题目: 给定一个有序（非降序）数组A，可含有重复元素，小于target的最大元素的位置，不存在则返回-1
*   博客：
**********************************/
#include <iostream>
using namespace std;

int BinarySearch(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    int index;
    // 求含重复元素中等于target的最小位置
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素左边元素等于目标元素
            if(mid - 1 >= 0 && A[mid - 1] == target){
                end = mid - 1;
            }//if
            else{
                return mid-1;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}

int main(){
    int A[] = {1,2,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearch(A,11,4)<<endl;
    return 0;
}

4.【给定一个有序（非降序）数组A，可含有重复元素，大于target的最小元素的位置，不存在则返回-1】

【题目】

给定一个有序（非降序）数组A，可含有重复元素，大于target的最小元素的位置，不存在则返回-1

【分析】

这个问题可以转换为给定一个有序（非降序）数组A，可含有重复元素，等于target的最大元素的后一位置，不存在则返回-1

【代码】
/*********************************
*   日期：2015-01-05
*   作者：SJF0115
*   题目: 给定一个有序（非降序）数组A，可含有重复元素，大于target的最小元素的位置，不存在则返回-1
*   博客：
**********************************/
#include <iostream>
using namespace std;

int BinarySearch(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    int index;
    // 求含重复元素中等于target的最大位置
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素右边元素等于目标元素
            if(mid + 1 < n && A[mid + 1] == target){
                start = mid + 1;
            }//if
            else{
                return (mid + 1 >= n)?-1:mid+1;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}

int main(){
    int A[] = {1,2,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearch(A,11,4)<<endl;
    cout<<BinarySearch(A,11,5)<<endl;
    cout<<BinarySearch(A,11,8)<<endl;
    return 0;
}

5.【给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数】

【题目】

给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数

【分析】

上面已经求出给定一个有序（非降序）数组A，可含有重复元素，求等于target最小位置和最大位置。

【代码】
/*********************************
*   日期：2015-01-05
*   作者：SJF0115
*   题目: 给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数
*   博客：
**********************************/
#include <iostream>
using namespace std;
// 求等于target的最小元素位置
int BinarySearchMin(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start <= end){
        int mid = (start + end) / 2;
        if(A[mid] == target){
            // 如果中间元素左边元素等于目标元素
            if(mid - 1 >= 0 && A[mid - 1] == target){
                end = mid - 1;
            }//if
            else{
                return mid;
            }
        }//if
        // 目标位于左半部分
        else if(A[mid] > target){
            end = mid - 1;
        }
        // 目标位于右半部分
        else{
            start = mid + 1;
        }//else
    }//while
    return -1;
}
// 求等于target的最大元素位置
int BinarySearchMax(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 二分查找变形
    while(start <= end){
        int mid = (start + end) / 2;
        // 中间元素等于目标
        if(A[mid] == target){
            // 如果中间元素右边元素等于目标元素
            if(mid + 1 < n && A[mid + 1] == target){
                start = mid + 1;
            }//if
            else{
                return mid;
            }//else
        }//if
        else if(A[mid] > target){
            end = mid -1;
        }//else
        else{
            start = mid + 1;
        }
    }//while
    return -1;
}

int BinarySearchCount(int A[],int n,int target){
    int min = BinarySearchMin(A,n,target);
    int max = BinarySearchMax(A,n,target);
    // 没有
    if(min == -1){
        return 0;
    }//if
    int count = max - min + 1;
    return count;
}

int main(){
    int A[] = {1,2,4,4,4,4,4,5,6,7,8};
    cout<<"Count->"<<BinarySearchCount(A,11,4)<<endl;
    return 0;
}

6.【给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的下标范围】

【题目】

给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的下标范围

【分析】

上面已经求出给定一个有序（非降序）数组A，可含有重复元素，求等于target最小位置和最大位置。

具体参考：[LeetCode]34.Search for a Range

【代码】
/*********************************
*   日期：2015-01-24
*   作者：SJF0115
*   题目: 34.Search for a Range
*   网址：https://oj.leetcode.com/problems/search-for-a-range/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> result;
        if(n <= 0){
            return result;
        }//if
        // 目标元素的最小位置
        int left = searchStartRange(A,n,target);
        // 目标元素的最大位置
        int right = searchEndRange(A,n,target);
        result.push_back(left);
        result.push_back(right);
        return result;
    }
private:
    // 目标元素的最小位置
    int searchStartRange(int A[],int n,int target){
        int start = 0,end = n-1;
        while(start <= end){
            int mid = (start + end) / 2;
            // 目标是中间元素
            if(A[mid] == target){
                // 如果中间元素左边元素等于目标元素
                if(mid - 1 >= 0 && A[mid - 1] == target){
                    end = mid - 1;
                }//if
                else{
                    return mid;
                }
            }
            // 目标位于右半部分
            else if(A[mid] < target){
                start = mid + 1;
            }//
            // 目标位于左半部分
            else{
                end = mid - 1;
            }
        }//while
        return -1;
    }
    // 目标元素的最大位置
    int searchEndRange(int A[],int n,int target){
        int start = 0,end = n-1;
        while(start <= end){
            int mid = (start + end) / 2;
            // 目标是中间元素
            if(A[mid] == target){
                // 如果中间元素右边元素等于目标元素
                if(mid + 1 < n && A[mid + 1] == target){
                    start = mid + 1;
                }//if
                else{
                    return mid;
                }
            }
            // 目标位于右半部分
            else if(A[mid] < target){
                start = mid + 1;
            }//
            // 目标位于左半部分
            else{
                end = mid - 1;
            }
        }//while
        return -1;
    }
};

int main(){
    Solution solution;
    int A[] = {1};
    int n = 1;
    int target = 0;
    vector<int> result = solution.searchRange(A,n,target);
    // 输出
    for(int i = 0;i < result.size();++i){
        cout<<result[i]<<endl;
    }//for
    return 0;
}

7.【给定一个有序（非降序）数组A，不含重复元素，求target在数组中下标位置，如果找不到，则返回插入位置】

【题目】

给定一个有序（非降序）数组A，可含有重复元素，求target在数组中下标位置，如果找不到，则返回插入位置。

【分析】

具体参考：[LeetCode]35.Search Insert Position

【代码】
/*********************************
*   日期：2015-01-24
*   作者：SJF0115
*   题目: 35.Search Insert Position
*   网址：https://oj.leetcode.com/problems/search-insert-position/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        if(n <= 0){
            return -1;
        }//if
        int start = 0,end = n - 1;
        // 二分查找
        while(start <= end){
            int mid = start + ((end - start) >> 1);
            // 目标找到
            if(A[mid] == target){
                return mid;
            }//if
            // 目标在左半部分
            else if(A[mid] > target){
                end = mid - 1;
            }//else
            // 目标在右半部分
            else{
                start = mid + 1;
            }//else
        }//while
        // 目标元素没有找到则找插入位置
        return start;// end + 1
    }
};

int main(){
    Solution solution;
    int A[] = {1,3,5,6};
    int n = 4;
    int target = 0;
    int result = solution.searchInsert(A,n,target);
    // 输出
    cout<<result<<endl;
    return 0;
}

8.【输入一个排好序的数组的一个旋转，输出旋转数组的最小元素】

【题目】

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

【分析】

具体参考：[经典面试题]输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。

【代码】
/*********************************
*   日期：2015-01-04
*   作者：SJF0115
*   题目: 输入一个排好序的数组的一个旋转，输出旋转数组的最小元素
*   博客：
**********************************/
#include <iostream>
using namespace std;

int SearchMin(int A[],int n){
    if(n <= 0){
        return -1;
    }//if
    int start = 0,end = n-1;
    // 数组有序
    if(A[end] > A[start]){
        return A[start];
    }//if
    // 数组旋转
    // 二分查找
    while(start <= end){
        int mid = (start + end) / 2;
        // [start,mid]有序[mid,end]无序
        if(A[mid] > A[start]){
            start = mid;
        }
        // [start,mid]无序[mid,end]有序
        else if(A[mid] < A[start]){
            end = mid;
        }
        else{
            return A[mid+1];
        }
    }//while
}

int main(){
    int A[] = {2,3,4,5,6,7,8};
    cout<<SearchMin(A,7)<<endl;
    return 0;
}

9.【输入一个排好序的数组的一个旋转，求target在数组中下标，没有重复元素】

具体参考：[LeetCode]33.Search in Rotated Sorted Array

/*********************************
*   日期：2014-01-15
*   作者：SJF0115
*   题号: 33.Search in Rotated Sorted Array
*   来源：http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;

class Solution {
public:
    //二分查找
    int search(int A[], int n, int target) {
        int start = 0,end = n-1;
        int mid;
        while(start <= end){
            mid = (start + end) / 2;
            if(A[mid] == target){
                return mid;
            }
            //中间元素大于最左边元素则左部分为有序数组
            else if(A[mid] >= A[start]){
                //目标位于左部分
                if(target >= A[start] && target <= A[mid]){
                    end = mid - 1;
                }
                //目标位于右部分
                else{
                    start = mid + 1;
                }
            }
            //中间元素小于最右边元素则右部分为有序数组
            else{
                //目标位于左部分
                if(target <= A[end] && target >= A[mid]){
                    start = mid + 1;
                }
                //目标位于左部分
                else{
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
};
int main() {
    int result;
    Solution solution;
    int A[] = {3,1};
    result = solution.search(A,2,1);
    printf("Result:%d\n",result);
    return 0;
}

10.【Find Minimum in Rotated Sorted Array]

[LeetCode]153.Find Minimum in Rotated Sorted Array

11.【Find Minimum in Rotated Sorted Array II ]

[LeetCode]154.Find Minimum in Rotated Sorted Array II

时间： 2024-11-08 18:14:20

[经典面试题]二分查找问题汇总的相关文章

一个经典的二分查找算法的Bug

1:     binarySearch([] a, key) {2:         low = 0;3:         high = a.length - 1;4: 5:         (low <= high) {6:             mid = (low + high) / 2;7:             midVal = a[mid];8:9:             (midVal < key)10:                 low = mid + 1;11: 

[经典面试题]在O(1)时间删除链表结点

[题目] 给定链表的头指针和一个结点指针,在O(1)时间删除该结点.链表结点的定义如下: struct ListNode {     int        value;     struct ListNode*  next; }; 函数的声明如下: void DeleteNode(ListNode* head,ListNode* node); [思路] 这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解. 在链表中

[经典面试题]子数组的最大乘积

题目 给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合乘积中的最大的一组,并写出算法的时间复杂度. 思路一 穷举法 我们把所有可能的(N-1)个数的组合找出来,分别计算它们的乘积,并比较大小.由于总共有N个(N-1)个数的组合,总的时间复杂度为O(N^2),但显然这不是最好的思路. 思路二 空间换时间 计算(N-1)个数的组合乘积,假设第i个(0<=i<=N-1)元素被排除在乘积之外(如下图). 设num[]为初试数组 Left[i]表示前i个元素(包括第i个

冒泡排序和二分查找

js的排序 我们这里只介绍一下冒泡排序法:[其它方法可以参考 php 的排序章节]     代码: <html> <head> <meta http-equiv="content-type" content="text/html;charset=utf-8"/>   <script type="text/javascript">   var arr=[0,-1,90,-18,900,90,78];

C#使用二分查找法判断指定字符的方法_C#教程

本文实例讲述了C#使用二分查找法判断指定字符的方法.分享给大家供大家参考,具体如下: private int sort_init(ref string[] chars, string str) //数组初始化 { string[] temp = str.Split(' '); //temp. chars = new string[temp.Count()]; int ndx = 0; int last_empty_positon = 0; foreach (string ch in temp)

PHP二分查找算法示例【递归与非递归方法】_php技巧

本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9

在MySQL中实现二分查找的详细教程_Mysql

给定一个升序排列的自然数数组,数组中包含重复数字,例如:[1,2,2,3,4,4,4,5,6,7,7].问题:给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现.注:连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定. 我为什么会出这道题目?     二分查找在数据库内核实现中非常重要     在数据库的内核实现中,二分查找是一个非常重要的逻辑,几乎99%以上的SQL语句(所有索引上的范围扫描/等值查询/Unique查询等),都会使用到二分查找进行数据的

算法：支持重复元素的二分查找

近几天在处理的一个项目,需要频繁对一些有序超大集合进行目标查找,二分查找算法是这类问题的最优解.但是java的Arrays.binarySearch()方法,如果集合中有重复元素,而且遇到目标元素正好是这些重复元素之一,该方法只能返回一个,并不能将所有的重复目标元素都返回,没办法,只能自造轮子了. 先复习下二分查找的经典算法: 1 private int binarySearch1(Integer[] A, Integer x) { 2 int low = 0, high = A.length

C语言编程中实现二分查找的简单入门实例_C 语言

架设有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素.数组中有个元素 x,如何知道 x 位于该数组的第几位呢? 解决这个问题的一个普遍方法就是二分查找法.下面是程序: #include <stdio.h> int binsearch(int x, int v[], int n); main() { int i, result, n; int wait; int x = 17; // 需要查找的数值 int v[19]; // 定义一个数组 // 给数组赋值 for(i = 0;