Last Updated: 27 Jun, 2016
Binary Search
Easy
Asked in companies
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)
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
Approaches
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):
- Int ‘n’ is the size of the array ‘nums’, and ‘target’ is the element we want to find.
- Initialize two variables, ‘s’ and ‘e’, initially assigned to ‘0’ and ‘n - 1’, respectively.
- 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’.
- Return -1.