surya_227 Array is not required , this will do it for(i=0;i scanf("%d",&input); if(input == key) printf("%d",i); }
adamk117 Yeah, good spot! Like most others, I initially parsed the input into an array to prepare it for a binary search. But, as you've pointed out, the input is coming in linearly so why not inline the search (for this particular problem). I guess it would be a different story if they asked for multiple searches on the same input though.
Antash I loled hard when you mentioned using binary search in an introduction to sorting tutorial :D
competitivecoder @surya_227 nice pic dude :)
danjb [deleted]
krobin_93 Just add one line to your solution to make it more efficient:
public static void main(String[] args) {
Scanner in = new Scanner(System.in); int goal = in.nextInt(); in.nextInt(); int counter = 0; while(in.hasNextInt()){ if(in.nextInt() == goal) { System.out.println(counter); break; } counter += 1; }}
danjb Yes, thank you!
carlosriverosv I think the comparision could be the condition of the while cycle:
public static void main(String[] args) {
Scanner scan = new Scanner(System.in); int search = scan.nextInt(); scan.nextInt(); int i = 0; while(scan.nextInt() != search){ i++; } System.out.println(i); }danjb Even shorter :)
krobin_93 The reduction in code here comes with a risk. If the input does not contain sufficient data(here int) , the code will fail as nextInt() will throw an Exception. Although input conditions are met in the test cases, in general,its always advised to check hasNextXXX() method before calling respective nextXXX() method to avoid any runtime exceptions or errors. Hope it meakes sense.
danjb While you are correct about that risk in general, in this special circumstance (programming competitions with valid input) we can omit this risk.
carlosriverosv Yes Krobin_93 you are right :). I only did this reduction due to the assumptions of the problem. In any other case should be as you already said.
MobilityWins Would you be able to explain this into C# or just explain what each line is doing, it has been so long since I have touch java and even then java was more complicated to me thant the other languages.
vikramkhalsa first it saves the goal (v), then it reads in n. Then it is reading in each integer as they come in and checking if it is v, while keeping count of how many it has checked and gotten so far. As soon as there is a match it prints the count so far.
duniya_ke_neta [deleted]
sayanarijit 30 points for this...!!!
v, n = input(), input() print(input().split().index(v))
jorgechiquinv C++ solution without using array.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int V, N, i; cin>>V>>N; N=0; while(cin>>i and i!=V) N++; cout<<N; return 0; }
elvis_dukaj It's better use the stl library
#include <iterator> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int key, sz; cin >> key >> sz; vector<int> a(sz); copy_n(istream_iterator<int>(cin), sz, begin(a)); cout << distance(begin(a), find(begin(a), end(a), key)); return 0; }
jorgechiquinv Yes, it seems more readable and scalable, but in my case I did it just for fun xD
#include <iostream> int main() { int V, N=0, i; std::cin>>V>>i; while(std::cin>>i && i!=V && ++N); std::cout<<N; return 0; }
praanj Since this is mentioned inside sorting problems, this should be done in O(log(N) using binary search.
int introTutorial(int V, vector arr) {
int start = 0; int end = arr.size() - 1; while(true) { int middle = (end + start) / 2; // integer division in C++ if(arr[middle] == V) return middle; else if(arr[middle + 1] == V) return middle + 1; else if(V < arr[middle]) end = middle; else start = middle; }}
ihebbensalem lovely python
v = int(input()) n = int(input()) print map(int,raw_input().strip().split(" ")).index(v)
bkvamsi99 my c code guys
include
include
include
include
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */ int V; int n; scanf(" %d", &V); scanf(" %d", &n); int i = 0; int found = 0; while(!found && i<n){ int curr; scanf(" %d", &curr); if(curr == V){ found = 1; printf("%d", i); } else{ i++; } } return 0;}
harshi_cuty855 why !found can u please explain
AkbarBJ_CEGian Python 3 version
p=eval(input()) n=eval(input()) lis=[int(x) for x in input().split()] print(lis.index(p))
Nomer I didn't bother using the array. Why write to memory? Also didn't bother typecasting strings to ints (I also solved in Python). Why incur the overhead of function calls? Not sure why some people are bothering with binary search either. Binary search may be O(log(n)), but the sorting algorithm you used on that not-preprocessed data was probably O(n log(n)). And many hard-coded their binary search because they couldn't or didn't want to use a built-in, which although useful practice for interviews is an off-by-one error nightmare.
int main() { int v, n; cin >> v >> n; for (int i=0; i < n; i++) { int val; cin >> val; if (v == val) { cout << i; break; } } return 0; }
smookerjee03 Your implementation, defeats the purpose of this example. This is about teaching an intro into how to think about searching techniques. Anyway never mind. :-)
harshana <?php $_fp = fopen("php://stdin", "r"); `$v=fgets($`_fp); `$n=fgets($`_fp); `$a=fgets($`_fp); `$ar=split(" ",$`a); sort($ar); for(`$i=0;$`i<`$n;$`i++){ if (`$v==$`ar[`$i]){$`num=$i;};} print $num; fclose($_fp); ?>output says no response but when i change like this
if (4==`$ar[$`i]){`$num=$`i;};}then it returns value of $i.. (test case0)
what is the problem???
drevilo Try sourcing each value from the input stream into a single array using 'fget()'. From there you might want to 'explode' a push into that array. You can easily recall that the first value will be in the 0,0 locale. From there it is trivial to search the array for that specific identifier.
lustigo Same problem here:
$_fp = fopen("php://stdin", "r");
_fp);
_fp);
_fp);
a);
$key = 0;
while (n){
`$v = $`arr[$key]; if(`$v == $`V){ echo $key; } $key ++;}
no Result, but when I echo V is the given number.
ashleypeacock Both ways of doing it are overcompliating it. Simply use http://php.net/manual/en/function.array-search.php - it can be done in a couple of lines of code.
lustigo $_fp = fopen("php://stdin", "r");
_fp);
_fp);
_fp);
a);
V, $arr);
echo $key;
doesn´t work either, i´m getting no output
ashleypeacock That's weird, this works for me (have to remove the random backticks, not sure where they are coming from!):
$fh = fopen("php://stdin", "r"); //What to search for fscanf(`$fh, '%d', $`v); //Length of array fscanf(`$fh, '%d', $`n); //Get the values to search through `$arrayValues = explode(' ', fgets($`fh)); //Find the key echo array_search(`$v, $`arrayValues);
edrouwendaal public int? BinarySearch(int[] A, int T) { // Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.[6] // 1. Set L to 0 and R to n − 1. // 2. If L > R, the search terminates as unsuccessful. // 3. Set m(the position of the middle element) to the floor of (L + R) / 2. // 4. If Am < T, set L to m + 1 and go to step 2. // 5. If Am > T, set R to m – 1 and go to step 2. // 6. Now Am = T, the search is done; return m. Array.Sort(A); int M; int L = 0; int R = A.Length - 1; while (L <= R) { M = (L + R) / 2; if (A[M] < T) L = M + 1; else if (A[M] > T) R = M - 1; else return M; } return null; }
Sort 175 Discussions, By:
Please Login in order to post a comment