Binary Search Algorithm - The Coding Shala

Home >> Algorithms >> Binary Search Algorithm

Binary Search Algorithm

A binary search is an algorithm used to search a given element in a sequence. Binary search works on the sorted array. We used the left and right index in search called the search space. In binary search, we find mid of left and right and check if our given element is in the first half or second and according to that we set new left and right. By doing this every time we eliminate half of the sequence.

let's take an example to implement the basic binary search.

Example 1:

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise, return -1.

Input: nums = [-1,0,3,5,9,12], target = 9

Output: 4

Explanation: 9 exists in nums and its index is 4

Input: nums = [-1,0,3,5,9,12], target = 2

Output: -1

Explanation: 2 does not exist in nums so return -1

Binary Search Algorithm Java Program

Here is the Java Program to implement the binary search algorithm.

Java Code: 

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(nums[mid]==target) return mid;
            if(nums[mid]>target) right = mid-1;
            else left = mid+1;
        }
        return -1;
    }
}

Time Complexity of Binary Search Algorithm

After every iteration, our search area became half decided by a midpoint. Either we go to the left side or right side of the midpoint. 

Time Complexity: O(log n).

Other Posts You May Like

• Time Complexity, Space Complexity, and Asymptotic Notations
• Median of two sorted arrays

Please leave a comment below if you like this post or found some error, it will help me to improve my content.