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.
binary search algorithm - The Coding Shala
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
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala