Binary Search Algorithm using java

Searching Algorithm :-

When you have to check or retrieve an element from the given data structure then we use searching algorithm.

It is two types :-

1. Sequential Search :- Here the list or array is traversed sequentially and every element is checked.
2. Interval Search :- Specifically designed for searching in sorted data-structures and are much more efficient than Sequential Search as they repeatedly target the center of the search structure and divide the search space in half.

Binary Search :-

It is a type of an efficient searching algorithm which is used for finding an element from a sorted array or list.

This sorted array can either be in ascending order or in descending order.

The idea behind binary search is that repeatedly dividing the array into halves until you’ve narrowed down the possible locations to just one.

Algorithm :-

1. Take four variables = start, end, middle, target.
2. Find the middle element of an array , Now your array is divided into two parts left and right.
3. If [ target element > middle element ] search in right part.
4. If [ target element < middle element ] search in left part.
5. If [ middle element == target element ] return that element.
6. If [ start > end ] element not found.

Time Complexity :-

• In each iteration or in each recursive call, the search gets reduced to half of the array.
• So for n elements in the array, there are log2n iterations or recursive calls.

Therefore, the Best Case, it means, if we get the element in 1st iteration only (middle element) = O(1) and for the Average Case and Worst Case = O(log2N).

Space Complexity is O(1).

Code Implementation :-

Binary Search Code Implementation

Explanation :-

1. Created one function named BinarySearch having the parameters of an array variable and the target element variable.
2. Initialize the start variable with value 0 and end variable with the value of arr.length -1 which means the last element of the array. Hence, here I am taking the starting and ending value of the sorted array.
3. Start a while loop with the condition that start value should always be less than or equal to the end value.
4. Then find the middle element with the given formula.
5. Now check the Binary Search cases which was also explained in the algorithm of it and if none of the value matches then simply return -1.
6. In the Driver Code, I have taken one sorted array and defined the target element whose index value needs to be find out and then calls the function.

This information is used to narrow the search. If you like this post, please leave a clap. Thank You !