Home Arrays Binary Search

Binary Search

by nikoo28
0 comment

Binary Search only works when your input list of elements is already sorted. This is main and the most important condition for this search algorithm. Unlike Linear Search, we take advantage of the sorted nature of the array. We always search in the middle portion of the array.

Working of Binary Search:

Let us say we have this sample array. Note that this array is sorted.

sample array to do binary search
Fig: Sample array and search target = 12

I want to search for the element 12 in this array. One way, I can proceed is by dividing the array in 2 halves. As soon as we break the array, you can see that we have a diversion between 13 and 15.

dividing array in 2 halves
Fig: Dividing the array in 2 halves

Note that we have to search for number 12. The right part of the array starts from 15. Because the array is sorted, you can easily conclude that all the elements in the right sub-array would be greater than my search query 12. So we can easily discard that part of the array. It is very likely, that we will find our result in the first part.

Once again, we can treat the first half of the array as a problem in itself. We can again divide it in 2 halves.

Image showing discarded parts of array.
Fig: Rejecting parts that don’t have our element.

As soon as we divide the left sub-array in 2 parts, we see the elements 6 and 7 at the divider. Since 12 is greater than 6, we can safely discard the left part of this sub-array. I hope this is now giving you an idea about how this technique works.

If you keep on repeating this process, eventually you will come at a division, where you can reach the desired element 12.

Image showing complete binary search.
Fig: Reaching our final target element

The algorithm therefore would look something like:

  1. Set the start position as beginning of array.
  2. Set the end position as the end of array.
  3. Start a loop
  4. Check the middle element. If it matches, we found our result.
  5. If (middle element > number to search), update the end position to mid.
  6. Else, update the first position.
  7. Repeat steps 46 until we find our element, or exhaust out of options.

Real life example:

Suppose you want to search a word in a dictionary. What we do is we directly go to some approximate page [say, middle page] and start searching from that point. If the word that we are searching is at the middle page, then we are done with the search.

However, if the alphabet is before the selected page then we apply the same process for the first half otherwise apply the same process to the second half.

So in a way we are again applying binary search, as we are dividing the problem into 2 halves. This is also known as the divide and conquer algorithmic paradigm.

Implementation:

static boolean binarySearch(int[] arr, int numberToSearch) { int left = 0; int right = arr.length - 1; while (left <= right) { // Find the mid index int mid = (left + right) / 2; // Check at mid index if (arr[mid] == numberToSearch) return true; // Update the terminal indices if (arr[mid] < numberToSearch) { left = mid + 1; } else right = mid - 1; } return false; }
Code language: Java (java)

Time Complexity: O( \log n)
Space Complexity: O(1)

The code and test cases can be found on GitHub.

Video Explanation:

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More