picking index of unspecified array size

[PopRockCandy]

Hi all, my question is how do I pick a specific number from an array which has an unspecified size efficiently? I'm sure I could traverse the array from the beginning or the end until I reach that number, but what would be realistic?

//lets say I have a user input a random number into an array
//Then asked afterwards to choose a index from that array of 
//their choice

std::cout << "input a number for array size:";
std::cin  >> size;

arr[size];

std::cout << "choose an index from arr that you want to display: ";

/*
    code that would allow user to find the index and its value
*/

[PopRockCandy]

So I realize now that what I am asking for is a search algorithm. what are some techniques or strategies to building an effective algorithm?

[Duthomhas]

You're using C++, so use the C++ library facilities.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
  // Here's a dynamic array of whatever your item type is.
  std::vector<item_type> items;

  // Populate it
  std::cout << "How many items? ";
  {
    int size;
    std::cin >> size;
    items.resize( size );
  }
  std::cout << "Please enter the items\n";
  for (auto& item : items)
    std::cin >> item;

  // Display one of the items
  std::cout << "Enter item index to display (1.." << items.size() << ")? ";
  {
    int n;
    std::cin >> n;
    if (n < 1 || n > items.size())
    {
      std::cout << "Invalid index!\n";
    }
    else
    {
      std::cout << "Item " << n << ": " << items[n-1] << "\n";
    }
  }

  // Search for an item
  std::cout << "Enter an item to find in the array? ";
  {
    item_type item;
    std::cin >> item;
    auto found = std::find( items.begin(), items.end(), item );
    if (found != items.end())
    {
      auto index = std::distance( found, items.end() );
      std::cout << "Item " << item << " is found at index " << (index + 1) << "\n";
    }
    else
    {
      std::cout << "\"" << item << "\" is not found in the array.\n";
    }
  }
}

Notice how we present the indices into the array as [1,N], lines 21 and 25. This is how people number things.

But C++ arrays are indexed as [0,N-1], so on line 31 we make that adjustment.

[edit] Almost forgot, but added search to the example. [/edit]

Hope this helps.

[jonnin]

c++ offers searching tools already as demonstrated.

But if you want to understand it... some things..

brute force: iterate over all the items until you find the thing. O(N). (vectors, arrays, hand rolled learning code). This is actually find and acceptable for data up to some size ... searching 10 items in a loop costs almost nothing on a modern machine. Searching 1/2 a billion this way stinks.

many searches against same data:
sort it first generally (N lg N) complexity, N is possible for certain data, and you can force other data into it sometimes, but call it NlgN. Then you can use the 'binary search' where you split the list in half, is in the upper or lower half (its sorted, so you know), repeat on the half you have left, ... repeat until you have 1 or 0 items left in the list. This is O(lg N). So you pay up front to sort it, but your searches forever after are cheaper, great if you sort once then do millions of searches. (vector sort and find routines or hand-rolled classroom code).

Hashing O(1) where you simply retrieve the data directly if it exists. One oversimplified example of this is to convert the data to a unique array location, check that location, it is there or it isnt. This isnt for searching arrays, but it is the best approach to data retrieval if your goal is to locate and get at data fast. Arrays(vectors) are better for iteration over all the data. Different containers for different uses... (C++ map or create your own)

[keskiverto]

std::cout << "input a number for array size:";
std::cin  >> size;
arr[size];
std::cout << "choose an index from arr that you want to display: ";

That is not functional code.

If you did mean:

int size = 0;
std::cin  >> size;
double arr[size];

This is not valid C++. The array's size must be set during compilation, and in the above example it is the user at runtime that makes the decision. (Some compilers support such thing, partly because C supports it now. C++ does not.)

The following is valid C++ and does what the user wants, unless the user want's too much:

constexpr int N = 42;
double arr[N];
int size = 0;
std::cin  >> size;
if ( N < size ) size = N;
// fill up to size elements of arr with values 

What is common for all of them is that the size is known. When the user wants an index of an element, the program already knows how many elements there are, because the program has already gotten that info from the user. The program simply has to store that fact somewhere (separate variable 'size' or the size property of std::vector).