我要招人

去企业版

首页 > 试题广场 >

非递归实现的binary_search

[编程题]非递归实现的binary_search

热度指数：218 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个有n个从小到大排序的且无重复的int序列,在数组中查找target并返回位置,如果不存在返回-1.(本题会人工改卷,请使用非递归实现的binary_search实现)

输入描述:

输入包含两行:
 第一行有两个整数n(1 ≤ n ≤ 100000000),表示数组数字个数n;target,即查找的目标值。 第二行为n个整数,范围均在32位整数,以空格分隔,保证输入数据合法

输出描述:

如果存在,输出target出现的下标,否则输出-1

示例1

输入

7 0 0 1 2 3 4 5 6

输出

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

int main(const int argc, const char** argv) {
  int n, target;
  fscanf(stdin, "%d %d", &n, &target);
  
  int i, nums[n];
  for (i = 0; i < n; ++i)
    fscanf(stdin, "%d", nums + i);
  
  int l = 0, m, r = n - 1;
  while (l <= r) {
    m = l + ((r - l) >> 1);
    if (target == *(nums + m))
      return fprintf(stdout, "%d\n", m), 0;
    if (target < *(nums + m)) r = m - 1;
    else l = m + 1;
  }
  
  return fprintf(stdout, "%d\n", -1), 0;
}

发表于 2021-08-05 12:51:37 回复(0)

元气の悟空

#include<stdio.h>
int a[100000000],n,i,target,l,r;
int main(){
    for(scanf("%d%d",&n,&target),i=0;i<n;i++) scanf("%d",a+i);
    for(l=0,r=n-1;l+1<r;){
        int mid=l+(r-l)/2;
        if(mid<=target) l=mid;
        else r=mid;
    }
    if(a[l]!=target&&a[r]!=target) printf("-1\n");
    else printf("%d\n",a[l]==target?l:r);
}

发表于 2017-11-01 14:46:57 回复(0)

美团内推码WncroPl

import java.util.Scanner;
/**
 * @author ranran
 * @version V1.0
 * @Title:
 * @Package First
 * @Description:
 * @date 2017/9/2 16:02
 */
public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int target = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }

        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (array[mid] == target) {
                System.out.println(mid);
                return;
            } else if (array[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }

        }
        System.out.println(-1);

    }


}

编辑于 2017-09-02 16:11:21 回复(0)

C++

牛客175026275号

#include <iostream>
#include <vector>
using namespace std;

int binary_search(const vector<int>* num_list, const int& n, const int& target)
{
if (num_list->size() < n)
{
return -1;
}
int min = 0;
int max = n;
int mid = (n - 1) / 2;
while (mid)
{
if (num_list->at(mid) == target) {
return mid;
}
else if (num_list->at(mid) < target)
{
mid = mid + (max - mid) / 2;
min = mid;
}
else {
mid = min + (mid - min) / 2;
max = mid;
}

if (min == max) {
return mid;
}
}
return -1;
}

int main()
{
int n = 0;
int target = 0;

if (cin >> n >> target)
{
// pass
}
else {
return 0;
}

int number = 0;
int count = n;
auto number_list = new vector<int>();
while (n--)
{
if (cin >> number)
{
number_list->emplace_back(number);
}
else {
return 0;
}
}

std::cout << binary_search(number_list, count, target) << std::endl;
number_list->clear();
delete number_list;
return 0;
}

发表于 2022-03-01 16:14:28 回复(0)

Cyllow

#include <iostream>
#include <vector>
using namespace std;
 
int binary_search(vector<int> nums, int search_num)
{
    int left = 0;
    int right = nums.size() - 1;
    int mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (nums[mid] == search_num)
            return mid;
        else if (nums[mid] > search_num)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}
 
int main()
{
    int vec_nums;
    int search_num;
    cin >> vec_nums >> search_num;
    vector<int> vec(vec_nums);
    for (int i = 0; i < vec_nums; i++)
        cin >> vec[i];
    cout << binary_search(vec, search_num) << endl;
    return 0;
}

发表于 2019-09-02 16:09:33 回复(0)

zhazhabin

include<iostream>

include<vector>

using namespace std;

vector<int> nVec;
int binary_search(int num,vector<int>::iterator beg,vector<int>::iterator end,int &nPos) {
vector<int>::iterator iterTemp = beg;
vector<int>::iterator mid = beg + (end - beg) / 2;
int OK = 1;
while (mid != num) {
if (end <= beg) {
OK = 0;
break;
}
if (mid > num) {
end = mid-1;
}
else {
beg = mid+1;
}
mid = beg + (end - beg) / 2;
//cout << "(" << beg << ", " << end << ", " << *mid << ")\n";
}
if(OK)
nPos = mid - iterTemp;
else
nPos = -1;
return nPos;
}
int main() {
int nSize,n;
cin >> nSize>>n;
int nTemp;
for (int i = 0; i < nSize; i++) {
cin >> nTemp;
nVec.push_back(nTemp);
}
int nPos = -1;
cout << binary_search(n,nVec.begin(), nVec.end()--,nPos) << endl;
return 0;
}

编辑于 2018-03-16 15:40:03 回复(0)

cute#

#include<iostream>
using namespace std;
int main()
{
    int n, target, i, tmp;
    tmp = 0;
    cin >> n;
    cin >> target;
    int a[n];
    for (i = 0; i<n; i++)
    {
        cin >> a[i];
    }
    for (int j = 0; j<n; j++)
    {
        if (target == a[j])
        {
            tmp++;
            cout << j << endl;
        }
    }
    if (tmp == 0)
    {
        cout << "-1";
    }

}

发表于 2017-09-24 17:37:34 回复(0)

不开口

#include<bits/stdc++.h>

using namespace std;

int FindVal(vector<int> &vec,int n)

{

int low = 0;

int high = vec.size()-1;

while(low <= high)

{

int mid = (low+high)/2;

if(n == vec[mid])

{

return mid;

}

if(n > vec[mid])

low = mid+1;

else

high = mid-1;

}

return -1;

}

int main()

{

int m;

int n;

cin>>m;

cin>>n;

vector<int> vec(m);

for(int i = 0 ; i < m ; ++i)

{

cin>>vec[i];

}

cout<<FindVal(vec,n)<<endl;

return 0;

}

发表于 2017-09-05 19:34:25 回复(0)

RomanMJ

set<int>::iterator Check(set<int> nums, const int &target){
    auto it = find(nums.begin(),nums.end(),target);
    if(it == nums.end())
          return -1;
    return it;
}

发表于 2017-09-02 23:15:50 回复(0)