Search algorithms are the essential part of the interviews. And there is a high possibility to face a search algorithm during an interview, tech stack independently. That’s why I decided to walk you through one of the most efficient searching algorithms.
The first round of the most common Interview questions was Sliding Window Technique. So, in Technical Interview Questions: Sliding Window Technique tutorial, I tried to solve a challenging most-asked question with this technique.
The winner of the second round indeed will be the Binary Search Algorithm.
What is Binary Search?
Binary Search is one of the most efficient searching algorithms with O(log n) time complexity for the worst-case scenario. If the central index matches the desired value, the best case time complexity would be O(1).
Other common names of Binary Search are Half-Interval Search and Logarithmic Search.
How Binary Search Works?
The binary search algorithm is working on the principle of repeatedly dividing the search interval in half and finding a target within this half. It compares the desired value to the middle element of the array. In case the middle element does not match the desired value, it will keep looking in half of the array and eliminate another half. To discard half of the array and apply Binary Search, the array must be sorted beforehand.
sortedArray = [1,4,5,7,9,13,22];
searchTarget = 9;
Iteration Start;
- Element at index 0 sortedArray[0]=1
- Last element at index 6 sortedArray[6]=22
- Middle element at index 3 is sortedArray[3]=7
- Is the middle element equals to the target ?
- 7==9? No!
- The target is greater than the middle element, so we can discard the left side of the array and continue to iterate the right side. The remained part of the array we need to consider = [9,13,22];
- The new middle is sortedArray[5]=13
- Is the middle element equal to the target?
- 13==9? No!
- The target is lower than the middle element, so we can discard the right side of the array and continue to iterate the left side.
- The remained part of the array we need to consider = [9];
- Is the middle element equal to the target?
- 9==9?
- Yes, the only remaining element in the array is equal to the target, finalizing the binary search iteration for this particular dataset.
- The target element has been found for the given array!
A Simplified Example of Binary Search
int[] sortedArray = {1, 4, 5, 7, 9, 13, 22};
int searchTarget = 9;
binarySearch(sortedArray, searchTarget);
public void binarySearch(int[] sortedArray, int searchTarget) {
int leftIndex = 0;
int rightIndex = sortedArray.length - 1;
while (leftIndex <= rightIndex) {
int middleElement = leftIndex + ((rightIndex - leftIndex) / 2);
if (sortedArray[middleElement] < searchTarget) {
leftIndex = middleElement + 1;
} else if (sortedArray[middleElement] > searchTarget) {
rightIndex = middleElement - 1;
} else if (sortedArray[middleElement] == searchTarget) {
System.out.println("Target element is found at index: " + middleElement);
break;
}
}
if (leftIndex > rightIndex) {
System.out.println("Target element is not found!");
}
}
Interviewing for a new job might cause anxiety and stress, but hey, you can prepare for most of the questions. Eventually, with a good plan, you can impress even the toughest interviewers with your successful performance. Feel free to follow the Exceptionly Tech Blog to keep yourself updated. Exceptionly Blog is challenging tools, best practices, and methodologies.
Check out some of my other posts that might help you with your interview preparation!
English 
Arabic
One Response