700238. Binary Search
Binary Search Slug: binary-search-1587115620 Difficulty: Easy Id: 700238 Topic Tags: Arrays, Searching, Divide and Conquer, Data Structures, Algorithms Company Tags: Infosys, Oracle, Wipro, Linkedin, Qualcomm, TCS, Cognizant, Accenture
Summary
The problem of Binary Search involves finding an element in a sorted array. The problem is to write an algorithm that takes a target value as input and returns the index of the target value in the array if it exists, or -1 if it does not exist. This problem is about using binary search to efficiently find elements in a sorted array.
Detailed Explanation
The approach for this problem is to use the concept of Binary Search. The idea behind binary search is that we start by comparing the target value with the middle element of the array. If the target value is less than the middle element, then we know it must be in the left half of the array. If the target value is greater than the middle element, then we know it must be in the right half of the array. We repeat this process until we find the target value or determine that it does not exist.
Here is a step-by-step breakdown of the solution:
- Start by finding the middle index of the array.
- Compare the target value with the element at the middle index.
- If the target value is equal to the element at the middle index, return the middle index as the result.
- If the target value is less than the element at the middle index, repeat the process for the left half of the array (i.e., from index 0 to mid-1).
- If the target value is greater than the element at the middle index, repeat the process for the right half of the array (i.e., from mid+1 to n-1).
- Repeat steps 2-5 until the target value is found or it is determined that it does not exist.
The time complexity of this algorithm is O(log n), where n is the number of elements in the array. This is because we divide the search space in half at each step, resulting in a logarithmic number of comparisons.
The space complexity of this algorithm is O(1), since we only need to keep track of a few variables (the middle index and the target value).
Optimized Solutions
Java
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}