Binary Search

LEVEL:Beginner

Description

Given a list of integers and a search value. Find the search value from the array using Binary Search Algorithm.

Input Format

First line contains the size of array (n), Second line contains the search value followed by n integers separated by spaces.

Output Format

Print the index of the search value if present else print -1 .


Example 1:

Input
5
3
1 2 3 4 5
Output
2
Example 2:

Input
6
28
34 46 33 25 67 45
Output
-1
Example 3:

Input
6
280
304 496 353 235 675 280
Output
5

oops

Login to see Discussion




Approach

Step-i) Take the input search value and array from the user.
Step-ii) Find the middle element of the array, If the middle element equals to the search value return the index of element.
Step-iii) Else If check whether the search value is less than or greater than the middle element.
Step-iv) If less than the middle value repeat steps (ii) and (iii) for left subarray, else greater than the middle value repeat steps (ii) and (iii) for right subarray.
Step-v) If the element doesn’t match in any process return -1 and terminate.

Time Complexity: O(log(n))
Space Complexity: O(1)


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






Sign Up Page
oops

Login to see solution/discussion