I recommend following along with if you want to see some examples and hear step by step how I coded binary search in Java! my video A few years ago, I was interviewing for a software engineering internship at a large tech company. I was asked a question and was able to implement the first part with ease. The interviewer followed up on that and asked me to code binary search. I remembered learning binary search in my data structures and algorithms course, but I could not remember how to code it. I frustratingly spent the next 25–30 minutes trying to remember how to code it. That was the day binary search became one of my . I learned that day that not knowing what binary search is or how to code it could cost you a job offer. To make sure none of you repeat my mistake, we will be going over what binary search is, how you code binary search in Java, and I’ll give tips on how binary search might come up in coding interviews. If this post is helpful, please consider or following me on Hackernoon for more content like this! must know algorithms for coding interviews subscribing to my YouTube channel Binary Search Explained Before we talk about binary search, it is important we understand the alternative: linear search. In linear search, we go through a list one element at a time, starting from the first element. We check if each value is the target value we are looking for. In the worst case, we go through the entire list, so this has an O(n) time complexity (don’t worry if you haven’t learned Big-O yet, it’s not necessary to understand binary search). Binary search improves on this but has two prerequisites. First, your input must have random access in O(1) time. This means we can access any element in our data structure in O(1) time. For this, we commonly use an array. Second, the input must be sorted. Once we’ve met those prerequisites, we’re ready to use binary search! With binary search, instead of starting at the first element in the array, we instead start in the middle. We check if that value is the target value. If it is, then we have found the number in our array. If the value is greater than our target value, we no longer need to consider it and all values to the right (at a greater index) because they are all larger than the middle value (this is why the input must be sorted). If the value is less than our target value, then we no longer need to consider it and all values to the left (at a lesser index) because they are all lesser than the middle value. We then repeat the algorithm on the portion of the array we are still considering. Binary Search Java Code Here is how you implement binary search recursively in Java: { (arr.length == ) { - ; } binSearchHelper(arr, num, , arr.length - ); } { (low == high) { arr[low] == num ? low : - ; } mid = low + ((high - low) / ); (arr[mid] < num) { binSearchHelper(arr, num, mid + , high); } (arr[mid] > num) { binSearchHelper(arr, num, low, mid - ); } { mid; } } /** * Performs binary search for num on arr recursively * arr is the input array that we are performing binary search on * num is the number we are searching for in arr * the index of num in arr or -1 if num is not present in arr */ @param @param @return public int binarySearch ( [] arr, num) int int // If array is empty, the element does not exist if 0 return 1 return 0 1 /** * Helper method for binary search * arr is the input array that we are performing binary search on * num is the number we are searching for in arr * low is the lowest index we are still considering * high is the highest index we are still considering * the index of num in arr or -1 if num is not present in arr */ @param @param @param @param @return private int binSearchHelper ( [] arr, num, low, high) int int int int // If only one index left to consider if return 1 // Start in the center of the portion of the array we are considering int 2 if // All elems to the left of index mid in arr are lesser return 1 else if // All elems to the right of index mid in arr are greater return 1 else // We found num return Here is how you implement binary search iteratively in Java: { (arr.length == ) { - ; } low = ; high = arr.length - ; (low != high) { mid = low + ((high - low) / ); (arr[mid] < num) { low = mid + ; } (arr[mid] > num) { high = mid - ; } { mid; } } arr[low] == num ? low : - ; } /** * Performs binary search for num on arr iteratively * * arr is the input array that we are performing binary search on * num is the number we are searching for in arr * the index of num in arr or -1 if num is not present in arr */ @param @param @return public int binarySearch ( [] arr, num) int int // If array is empty, the element does not exist if 0 return 1 // The lowest and highest indices we are still considering int 0 int 1 while int 2 if 1 else if 1 else return // If only one index left to consider return 1 Binary Search in Interviews There are three key things that you should keep in your mind when you’re considering using binary search in a coding interview. If your input is not sorted, only use binary search if your time complexity is worse than O(n*log(n)). This is because the worst case time complexity for the most optimal comparison-based sorting algorithms (like merge sort) is O(n*log(n)). Therefore, if you have a time complexity of O(1), O(n), or O(n*log(n)), you won’t get any value from using binary search if your input is not sorted. Think about whether you can use binary search in cases where you are using linear search. It is in these cases that we may be able to replace that linear search lookup with binary search. Pay close attention to the constraints that the interviewer gives to you. If the input to your problem is sorted, there is usually a reason why. This should immediately make you think about whether you can use binary search as part of your solution. I hope you found this story informative! Please share it with a friend you think might benefit from it as well! If you liked the post/video, feel free to leave a clap/like and follow/subscribe to my for more content like this. Also, for updates on when I am posting new content. I hope to see you all on the next one! YouTube account follow me on Twitter Previously published at https://levelup.gitconnected.com/binary-search-cbc0c4ed72f5
