我要招人

去企业版

首页 > 试题广场 >

比如一个数组[1,2,3,4,6,8,9,4,8,11,18

[问答题]

比如一个数组[1,2,3,4,6,8,9,4,8,11,18,19,100] 前半部分是是一个递增数组，后面一个还是递增数组，但整个数组不是递增数组，那么怎么最快的找出其中一个数？

牛客304487号

首先找到两个递增序列的分界点，之后对两个递增序列分别使用二分查找

具体代码如下：

 int binary_search(int* a, int low, int high, int goal)    //二分查找  
{  
    while(low <= high)  
    {  
        int middle = (low+high)>>1;    //(low+high)/2  
        if(a[middle] == goal)  
            return middle;  
        else if(a[middle] < goal)  
            low = middle + 1;    
        else  
            high = middle - 1;  
    }  
    return -1;  
}  
void getNum(int *a, int len, int goal)  
{  
    int i, index;  
    for(i = 0; i < len-1; i++)  
    {  
        if(a[i] > a[i+1])      
            break;  
    }  
    if(a[i] >= goal)           
    {  
        index = binary_search(a, 0, i, goal);  
        printf("%d\n",index);  
    }  
    if(a[i+1] <= goal)         
    {  
        index = binary_search(a+i+1, 0, len-i-2, goal);  
        if(index != -1)  
            index += (i+1);    
        printf("%d\n",index);  
    }  
}

编辑于 2015-06-21 09:40:14 回复(0)

SunburstRun

中心思想就像归并一样，先找到二个递增序列的临界点，然后分开在2个序列里面查找，最后归并看那边有这个数，可以都有，也可以都没有

发表于 2015-06-21 10:48:10 回复(0)

老张

不需要找到两个数组的临界点，直接利用二分法剪枝。规则如下：

1.找到数组的的中间点与要查找的数字比较，如果是要查找的数则查找成功，如果不是转2

2.比较这个数与中间点的大小，如果大于中间节点并且大于最后一个节点那么这个数字就是不存在的；如果这个数字大于中间节点并且小于最后一个节点那么这个数字就是在中间节点与最后一个节点之间，那么将其实节点设置为刚才的中间节点继续循环查找即可。如果这个数字比中间节点小转到3

3.这个数字比中间节点小，并且比最后一个节点也小那么就是不存在数组中，如果比中间节点小但是比第一个节点大的话那么就是在第一个节点与中间节点直接，将最后一个节点设置为中间节点，继续循环找到即可。

4知道第一个节点和最后一个节点是同一个节点还是找不到该节点就结束，说明这个值不在数组当中。

发表于 2015-06-21 12:12:39 回复(4)

大黑熊

while（当前元素比前一个元素大）
判断是否是查找的数，是的话返回
循环终止又没返回表示找到临界点，直接对后面序列进行二分法查找即可

发表于 2017-03-24 00:57:26 回复(0)

你正年轻

剑指offer面试题8：旋转数组的最小数字

#include "stdafx.h"
#include<exception>

int MinInOrder(int* numbers, int index1, int index2);

int Min(int* numbers, int length)
{
    if(numbers == NULL || length <= 0)
        throw new std::exception("Invalid parameters");
 
    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;
    while(numbers[index1] >= numbers[index2])
    {
        // 如果index1和index2指向相邻的两个数，
        // 则index1指向第一个递增子数组的最后一个数字，
        // index2指向第二个子数组的第一个数字，也就是数组中的最小数字
        if(index2 - index1 == 1)
        {
            indexMid = index2;
            break;
        }
 
        // 如果下标为index1、index2和indexMid指向的三个数字相等，
        // 则只能顺序查找
        indexMid = (index1 + index2) / 2;
        if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
            return MinInOrder(numbers, index1, index2);

        // 缩小查找范围
        if(numbers[indexMid] >= numbers[index1])
            index1 = indexMid;
        else if(numbers[indexMid] <= numbers[index2])
            index2 = indexMid;
    }
 
    return numbers[indexMid];
}

int MinInOrder(int* numbers, int index1, int index2)
{
    int result = numbers[index1];
    for(int i = index1 + 1; i <= index2; ++i)
    {
        if(result > numbers[i])
            result = numbers[i];
    }

    return result;
}

编辑于 2015-06-21 20:42:00 回复(0)

小菜一枚


	int binary_search(int *a,int low,int high,int goal)
{
 while(low <= high)
 {
   int middle = (low+high)>>1;
   if(a[middle] == goal)
    return middle;
   else if(a[middle] > goal)
    high = middle-1;
   else
    low = middle + 1;
 }
 return -1;
}
void getnumber(int *a,int len ,int goal)
{
 int i;
 for(i = 0 ; i < len ;i++)
 {
       if(a[i] == goal)
    {
     cout<<i;
     return;
    }
    if(a[i] > a[i+1])
     break;
 }
     int low = i+1;
  int high = len-1;
  int num;
  if((num = binary_search(a,low,high,goal))>=0)
   cout<<num;
  else
   cout<<"no such data";



	}

首先对前一半递增直接查找，找到即退出，后一半二分查找

编辑于 2015-06-21 19:32:57 回复(0)

Miner_Sty

#include <iostream>
using namespace std;

int main() {
    int a[] = {1,2,3,4,6,8,9,4,8,11,18,19,100};
    int tag=0, n;
    int len = sizeof(a) / sizeof(int);
    cin >> n;
    while (a[tag] && a[tag]<a[tag+1]) {
        if (a[tag] == n) {
            cout << tag << endl;
            return 0;
        }
        tag ++;
    }
    int low = tag+1, high = len-1, mid = (low + high)/2;
    while (low <= high) {
        if (a[mid] == n) {
            cout << mid << endl;
            return 0;
        } else if (a[mid] < n) {
            low = mid + 1;
            mid = (high + low)/2;
        } else {
            high = mid - 1;
            mid = (low + high)/2;
        }
    }
    cout << "Can't find it !!" << endl;
    return 0;
}

发表于 2015-06-21 10:35:03 回复(0)

夏雨天

先找到这个数组的中，两个递增数组的分界点，然后分别利用二分法进行查找。

发表于 2015-06-21 00:38:19 回复(0)

weizier

1.可以先归并这两个数组，然后再利用二分查找法找到这个数。时间复杂度为O(N),空间复杂度为O(N)

2.如果事先知道这两部分的分界，则可以分别去这两部分用二分查找。时间复杂度为O(logN),空间复杂度为O(1).如果不知道，则可以先用O(N)的时间复杂度找到分界点，然后再利用二分查找。

发表于 2015-06-21 00:19:59 回复(0)

提交观点

问题信息

分治盛趣游戏

上传者：LingYu

难度：

9条回答 0收藏 20588浏览

比如一个数组[1,2,3,4,6,8,9,4,8,11,18

问题信息

热门推荐

相关试题