## Introduction

Searching and sorting form an important part of placement preparation; this is the first topic most people start with. In simple terms, searching means retrieving any element from any data structure or a collection of items. A good example of searching is whenever you find any occurrence of a particular word in Microsoft Word or Google docs.

Binary search is the most widely used searching algorithm used to search an item from a sorted list; It is also known as half interval search, logarithmic search, and binary chop. Using binary search takes the time complexity of O(log N) as compared to linear searching an item that takes the time complexity of O(N), where N is the number of items in the search space. This blog will discuss Binary Search program in Java.

Also, See - __Iteration Statements in Java____, ____Duck Number in Java__

## Binary Search Java - Understanding The Problem Statement

The problem statement on hand is, "Given a list of items in sorted order, find the occurrence of an element x in this list."

Before moving on to the algorithm and Binary search program in __Java__, let's understand the essence of binary search in a little more detail. Lets try to decode the possible position of a target element considering that we are currently at any random position in the list of items.

If you are at a particular element and the target element is greater than the current one in a sorted list of items. The target element would be present in the right of the current element.

Similarly, if you are searching for an element and the current element is greater than the target element. The target element will be somewhere on the left of the current element.

The question arises, how to choose a current element by which we can compare?

A simple solution is to take any particular element as the current one and then search operation. However, in the worst-case scenario, taking any random element as the current element will make the time complexity O(N). So we are not properly utilizing the fact that the array is sorted. To make the search process effective,** **

**Binary search searches for a particular element by comparing the middlemost item of the list of items**; if the element is found at the middle position, then the index of the item is returned; otherwise, if the target element is greater than the item in the middle, then we search in the sub-array to the right of the middle. If the target element is less than the element at the middle, we search in the sub-array to the left of the middle element.

An important point to note is that binary search only works for sorted lists of items, so you cannot use binary search if the list of items is unsorted. You can obviously sort the list of items first using any sorting algorithm and then apply binary search; however, this will make the time complexity O(NLogN) + O (LogN), O(NLog N) for searching, and O(log N) for binary search, making the time complexity greater than linear search.

Binary Search Java is not straightaway asked in an interview, instead it's a general pattern. Questions related to this pattern are prominently asked. A general rule of thumb is whenever you are given a sorted sequence of items, the interviewer is giving you a hint that somehow you have to use binary search. Letâ€™s now look at algorithm, examples and code for Binary Search Java.

### Binary Search Algorithm Java

- Take two pointers, left equal to 0 and right equal to the size of the list for the leftmost and the rightmost element of the list of items.
- Find the middle index, using the formula
- middle = left + (right-left)/2.
- Compare the target element with the element at the middle position.
- If the target element equals the middle element, the element is found. You can return the index of the element.
- If the target element is greater than the middle element, you need to search in the subarray from the middle element to the rightmost element.
- Else you need to search in the range from the leftmost element to the middle element.

### Example for Binary Search Program in Java

Letâ€™s take an array of 5 items to understand this algorithm.

arr[] = {10, 13, 34, 45, 56, 60, 70}

You are required to find 56 in this list. The left pointer will be at index 0, and the right pointer will be at the 6th index. The middle pointer will be at

left + (right-left)/2 = 0 + (6-0)/2 = 0 + 3 = 3rd index. The position of pointers is shown in the diagram below.

Since we are only concerned with the subarray to the right of the middle, we will now apply binary search in this subarray. The left, right, and middle pointer position is shown below.

The element at the middle position is 60, greater than the target element 56. So we will now search in the left half of the middle. The left, right, and middle pointer position is shown below.

The pointers at left, right, and middle positions point to the same index, and also the element is also the same as the target element. Hence the element is found. It's highly recommended to try out this algorithm on your own by taking some random examples and then moving to the implementation.

Since we now know the algorithm and practice with an example, let's jump to implementing Binary Search in Java.

Also see, __Hashcode Method in Java____ __ and __Swap Function in Java__