Binary Search

Easy
0/40
Average time to solve is 15m
profile
Contributed by
949 upvotes
Asked in companies
OraclePaytm (One97 Communications Limited)Cisco

Problem statement

You are given an integer array 'A' of size 'N', sorted in non-decreasing order. You are also given an integer 'target'. Your task is to write a function to search for 'target' in the array 'A'. If it exists, return its index in 0-based indexing. If 'target' is not present in the array 'A', return -1.


Note:
You must write an algorithm whose time complexity is O(LogN)


Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line contains an Integer 'N', which denotes the size of the array/list.

The second line contains 'N' single space-separated integers representing the elements in the array/list.

The third line contains the value of 'target' to be searched for in the array/list.
Output Format :
Return the index at which 'target' is present for each test case, -1 otherwise.
Constraints :
1 <= N <= 10^5
1 <= A[i] <= 10^9
1 <= target <= 10^9
Time Limit: 1 sec
Sample Input 1:
7
1 3 7 9 11 12 45
3
Sample Output 1:
1
Explanation of sample output 1:
nums = [1, 3, 7, 9, 11, 12, 45],
The index of element '3' is 1.
Hence, the answer is '1'.


Sample Input 2:
7
1 2 3 4 5 6 7
9
Sample Output 2:
-1
Explanation of sample output 2:
nums = [1, 2, 3, 4, 5, 6, 7],
Element '9' doesn't exist.
Hence, the answer is '-1'.


Hint

Apply Binary Search.

Approaches (1)
Binary Search

Since our array is sorted, we can apply binary search here. We will keep two variables, ‘s’ and ‘e’, initially assigned to ‘0’ and ‘length of the array’, respectively. At each iteration, we will first calculate the middle value of ‘s’ and ‘e’ and store it in a variable called ‘mid’. Then we will check the following conditions:

  • nums[mid] == target:
    We have found our answer in this case, so that we will return the index.
  • nums[mid] > target:
    In this case, the current value is greater than the ‘target’, so we will go to the smaller values.
  • nums[mid] < target:
    In this case, the current value is smaller than the ‘target’, so we will go to the larger values.
     

If we don’t find any index, we will return ‘-1’.

 

The steps are as follows:-
 

// Function to find the element ‘target’

function search(int[] nums, int n, int target):

  1. Int ‘n’ is the size of the array ‘nums’, and ‘target’ is the element we want to find.
  2. Initialize two variables, ‘s’ and ‘e’, initially assigned to ‘0’ and ‘n - 1’, respectively.
  3. while ‘s <= e’:
    • Initialize a variable ‘mid’, and assign it to ‘(s + e) / 2’.
    • If ‘nums[mid] == target’:
      • Return ‘mid’.
    • else if ‘nums[mid] > target’:
      • Assign ‘e’ to ‘mid - 1’.
    • else:
      • Assign ‘s’ to ‘mid + 1’.
  4. Return -1.
Time Complexity

O( N * logN ), where 'N' is the size of the array ‘nums’.

 

We are using the binary search here,

 

Hence the time complexity is O( N * logN ).

Space Complexity

O( 1 ).

 

We are only using some variables,


Hence the space complexity is O( 1 ).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Binary Search
Full screen
Console