!(https://hackernoon.com/hn-images/1*DOR__3reJYPwGuyytG520g.jpeg)\n\nI hope we all have some idea about what binary search is and does. But I’m not going to explain the algorithm step by step, rather I’m going to give an insight into how binary search works and can be used.\n\nCheck out: [geeksforgeeks.org/binary-search](http://geeksforgeeks.org/binary-search) if you’re unaware of Binary Search.\n\nGiven a sorted array, we find the middle-most element and check the element with the key. If the middle-most element is equal to key, we’ve found the key. If the middle-most element is greater than the key, we search on the left half of the middle-most element, else we search on the right half.\n\nHere’s an iterative code for Binary Search in Java\n\nNotice that in line 6, we use\n\nint mid = (low + high) / 2;\n\nBut calculating mid this way is ineffective. Why? Let’s take an example. \nLet us take integers from an integer low to an integer high (both included).\n\nNotice the mids computed by formulae in 3rd and 4th columns.\n\n* for low = 3 and high = 11, the number of elements (#elements) = 9 \n So there is only 1 mid, i.e., 7 \n \\* Both formulae have computed the mid correctly\n* for low = 3 and high = 10, #elements = 8 \n So there are 2 mids, 6 (lower mid) and 7 (higher mid) \n \\* Both formulae have computed the lower mid correctly\n* for low = -11 and high = -3, #elements = 9 \n So there is only 1 mid, i.e., -7 \n \\* Both formulae have computed the mid correctly\n* for low = -10 and high = -3, #elements = 8 \n So there are 2 mids, -7 (lower mid) and -8 (higher mid) \n \\* The formula`(low + high) / 2` has failed to compute the lower mid correctly but the other formula has computed it correctly.\n\nSo, we should always use the below formula to compute lower mid as it is much more reliable:\n\nint mid = low + ((high - low)/2);\n\nWhen #elements = odd, we have only 1 mid. So we can use the above formula to compute mid. \nWhen #elements = even, the above formula only gives the lower mid. \nThe higher mid can be computed by the below formula:\n\nint mid2 = low + ((high - low + 1) / 2);\n\nNow, the interesting part…\n\nLet’s go back to the iterative code for Binary Search. Notice three things. \n1\\. How we are moving low and high \n2\\. How we are computing mid \n3\\. The condition in while loop\n\nThe beauty of Binary Search lies in these three things alone. Let us explore this further.\n\nFor a simple binary search where we just have to find the element in the array, \nwe use the following: \n1\\. `low = mid - 1` for moving `low` \n2\\. `high = mid + 1` for moving `high` \n3\\. `mid = low + ((high - low) / 2)` (why? discussed above) \n4\\. `low <= high` in the while loop\n\nIs it always the case that we use the same conditions for binary search? \nIt depends…on our problem statement.\n\nExample #1:\n\nGiven an integer x, find the maximum element y in an array of size N that satisfies the condition `y <= x`\n\nSolution:\n\nWe know that x might not be in the array. So the simple binary search for x in the given array won’t work. But for binary search, all we know is x, the key. We need to find the element in the array that’s the closest to x and less than or equal to x (if it exists).\n\nThree things should always come to your mind when using binary search: \n1\\. How should we move low and high? \n2\\. How should we compute mid? \n3\\. What would be the condition in while loop?\n\n_We always start with ‘How to move low and high?’ and then find out how to compute mid and what might be the while condition. NOT the other way round._\n\n1. _How to move low and high?_ \n When `array[mid] < x` , there is a possibility that the current element might be the answer (since y can be less than x). \n So, we shouldn’t discard mid while moving low. \n Hence, low becomes `low = mid` , not `low = mid + 1` \n High remains the same as it is irrelevant to our problem statement.\n2. _How to compute mid? \n _When we use `mid = low + ((high - low) / 2)` , we are calculating the lower mid. So when the #elements in the array is even, the \n `if(array[mid] > x)` becomes false, so control will go to else clause where `low = mid` . This results in an infinite loop. (why? take an example) \n Hence, we take the higher mid, i.e., `mid = low + ((high - low + 1) / 2)`\n3. _What would be the condition in while loop? \n _Since we are storing the maximum element that is less than or equal to x in low, we should stop when low = high and return `array[low]` or `array[high]`. Hence, the condition in while loop is `low < high` .\n\nThe Solution in Java looks like this:\n\nExample #2:\n\nGiven an integer x, find the minimum element y in an array of size N that satisfies the condition `y >= x`\n\nSolution:\n\nUsing a similar analytical approach we used in example 1 (try it out yourself), we can say that\n\n1. `low = mid + 1` for moving low\n2. `high = mid` for moving high\n3. `mid = low + ((high - low) / 2)` for calculating mid\n4. `low < high` for the condition in while loop\n\nHence we can tabulate different scenarios of using Binary Search as follows:\n\nFeel free to experiment with these conditions and I hope you have gotten some insight into how to use binary search.\n\nNamaste!