BSEARCH1 - Binary search

no tags 

You are given a sorted array of numbers, and followed by number of queries, for each query if the queried number is present in the array print its position, else print -1.

Input

First line contains N Q, number of elements in the array and number of queries to follow,

Second line contains N numbers, elements of the array, each number will be -10^9<= ai <= 10^9, 0 < N <= 10^5, 0 < Q <= 5*10^5

Output

For each element in the query, print the elements 0 based location of its first occurence, if present, otherwise print -1.

Example

Input:
5 4
2 4 7 7 9
7
10
4
2

Output:
2
-1
1
0

hide comments
marsar24: 2018-10-12 18:19:09


My code runs fine on other IDEs. Why is it returning error SIGSEV something?





/*
Problem Statement
You are given a sorted array of numbers, and followed by number of queries, for each query if the queried number is present in the array print its position, else print -1.

Input
First line contains N Q, number of elements in the array and number of queries to follow,

Second line contains N numbers, elements of the array, each number will be -10^9<= ai <= 10^9, 0 < N <= 10^5, 0 < Q <= 5*10^5

Output
For each element in the query, print the elements 0 based location of its first occurence, if present, otherwise print -1.

*/

#include <iostream>
#include <stdio.h>

using namespace std;
int A[1000];

int find_binary( int number_of_element, int x )
{
/*
1. Sort the array in ascending order. Also initialize left and right index variables.
2. Find the middle element.
3. Compare the search element to the middle element. If middle element == Search element; STOP. Else follow Step 4, 5 and 6.
4. If the middle element is bigger than the search element; Left side is to be searched. New Right element becomes: (Middle Element - 1)
5. If the middle element is smaller than the search element; Right side is to be searched. New Middle element becomes: (Middle Element + 1)
6. If left > Right; Stop;Element not Found; return -1
7. Repeat steps 3, 4, 5 and 6.
*/

/// Step 1: Our Input is already sort. We will incorporate sorting techniques after basic sorting lecture.
/// Step 2: Finding middle element

int left_index =0;
int right_index = number_of_element;

while (left_index <= right_index)
{
int middle_index = (left_index + right_index )/2;

/// Step 3: If middle element == Search element
if ( A[middle_index] == x ) return middle_index;

/// Step 4: If the middle element is bigger than the search element
if ( A[middle_index] >= x ) right_index = middle_index -1;

/// Step 5: If the middle element is smaller than the search element
else left_index = middle_index + 1;

} return -1; /// Step 6: Element not Found
}


int main()
{
int number_of_elements = 0, number_of_queries = 0;

scanf("%d%d", &number_of_elements, &number_of_queries);

// I am heading towards n + n*log(n) === n*log(n) complexity. Am I correct?


for (int i=0; i < number_of_elements; ++i) scanf("%d", &A[i]);

for (int j=0; j < number_of_queries; ++j)
{
int index_found = 0;
int item_to_be_searched = 0;

scanf("%d", &item_to_be_searched);

index_found = find_binary( number_of_elements, item_to_be_searched);

printf("%d \n", index_found);
}

return 0;
}

one_piece_: 2018-06-30 22:19:21

read the comments till end.

code0monkey1: 2018-06-12 13:19:18

hint : lower_bound gives the iterator to the first element in the array that is equal or GREATER than the number being searched . ( so you could get a valid index in return even though the element would not be present in the array, so you need to check if the iterator points to the number actually being searched to validate the answer )

caro_linda2018: 2018-05-29 03:15:19

Go to hell this stupid TLE thing, just because I didn't write scanf and printf.

pallindromeguy: 2017-12-27 15:30:02

Simple binary search and arrays worked for me along with scanf/printf

kundan_2508: 2017-10-11 21:16:17

it is giving run time error..how can i remove it?

mustella: 2017-09-06 17:59:01

Remember: it's a SORTED vector as input.
I've ignored that and got TLE.

Last edit: 2017-09-06 18:00:39
a_kk: 2017-08-27 22:27:46

python is giving TLE :(
how can i remove it..

dunjen_master: 2017-08-25 23:17:41

can use map..AC in 0.29 seconds

r19: 2017-08-08 10:15:21

Last edit: 2018-02-02 04:52:47

Added by:jack(chakradarraju)
Date:2012-03-13
Time limit:0.160s-0.320s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:NITT Class