# Binary search in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

In this post, we will see how to perform binary search in java using divide and conquer method.When you want to find a value in sorted array, we use binary search and we will also see how to compute time complexity of binary search.
Lets say we have an sorted array.

#### Algorithm:

1. Initialize `first=0` and `last=sortedArray.length-1`
2. compute mid and compare `sortedArray[mid]`  with element to be searched
3. If element to be searched is less than `sortedArray[mid]` then element lies in left part of the mid, so `last=mid-1`
4. if element to be searched is greater than `sortedArray[mid]` then element lies in right part of the mid, so `first=mid+1`.
5. if element to be searched is equal to `sortedArray[mid]`, then return index
6. Repeat above process until first is less than last.
Example:
Now lets assume our sorted array is:
and we want to search for 74 in above array. Below diagram will explain how binary search will work here.

When you observe closely, in each of the iteration you are cutting scope of array to the half. In every iteration, we are overriding value of first or last depending on `sortedArray[mid]`.

So for
0th iteration : n
1th iteration: n/2
2nd iteration n/4
3rd iteration n/8.

Generalizing above equation:
For ith iteration : n/2i

So iteration will end , when we have 1 element left i.e. for any i, which will be our last iteration:

1=n/2i;
2i=n;
after taking log
i= log(n);

so it concludes that number of iteration requires to do binary search is log(n) so complexity of binary search is log(n)
It makes sense as in our example, we have n as 8 . It took 3 iterations(8->4->2->1) and 3 is log(8).
Code:

when you run above program, you will get below output:

Index of 74 in array is: 2
Index of 7 in array is: -1

That’s all about binary search in java

import_contacts

### You may also like: ## Related Posts

• 04 June

### Search for a range Leetcode – Find first and last position of element in sorted array

Table of ContentsApproach 1 (Using Linear Search)Approach 2 (Using Modified Binary Search-Optimal) In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is […]

• 28 March

### Sort an array of 0s, 1s and 2s

Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to sort an array of 0s, 1s and 2s.We have already seen a post on sort 0s and 1s in an array. Problem Given an array containing zeroes, […]

• 04 March

### Check if it is possible to reach end of given Array by Jumping

Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. ﻿ ﻿ Problem Given an array with positive integers as elements indicating the maximum length of a jump which can be made from any position in the array. Check if it is possible to have […]

• 17 February

### Check if Array Elements are Consecutive

Table of ContentsProblemSolutionProgram to check if Array Elements are Consecutive If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs. In this post, we will see how to check if array elements are consecutive. Problem Given an array, we need to check if array contains […]

• 01 November

### Find the local minima in array

Table of ContentsProblemSolutionNaive approachEfficient approach If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find the local minima in the array. Problem An element is local minima if it is less than its neighbors. int [] arr = {10, […]

• 22 October

### Sliding Window Maximum in java

Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see about Sliding Window Maximum in java Problem Given an Array of integers and an Integer k, Find the maximum element of from all the contiguous subarrays of size K. […]

1. Manoj says: