Binary Search Algorithm Java | Fresher Interview

Binary search is a divide-and-conquer way to find a value in a sorted array, and it runs in O of log n time. I keep two pointers, left at the start and right at the end of the array. In each step I look at the middle element. If it equals my target, I'm done and I return that index. If the target is smaller than the middle, then because the array is sorted I know it can only be in the left half, so I move right to mid minus one. If the target is larger, it must be in the right half, so I move left to mid plus one. I repeat until I either find the value or the pointers cross, which means it isn't there. The reason this is so fast is that every single comparison throws away half of what's left, so even a million elements only take about twenty comparisons, compared to up to a million for a plain linear scan. Two things I'm always careful about as a fresher. First, I compute the middle as left plus the quantity right minus left divided by two, instead of left plus right divided by two, because adding two large indices can overflow an int and wrap to a negative number. Second, the array genuinely has to be sorted first, otherwise the middle element tells me nothing about which side to keep, and the whole elimination idea breaks down. The iterative version uses constant extra space; the recursive version uses O of log n space for the call stack.