DSA - Binary Search

Binary search
It's an algorithm which is optimized way to find a element in array.
let's take an example array which is sorted.
arr[] = {1,2,3,4,5,6};

Here target is to find 5.

first it will take no of index here 5 after it will take half of the index = 2 the element in 2 index is 3. 3 is lesser then 5 again from index 3 to 5 it will take the half. If the element 4 is greater than target it will search from index 0 to 2. Now index is 4 and element is 5. and 5 is equal to target and it prints the output.

Example

arr[] = {1,5,7,9,10,15}; target = 10;

1st - index = 5
Start = 0 end= 5
binary search = 0+5/2 -> 2(index)

Value in index 2 is 7 and 7 is lesser than target.

2nd - {9,10,15}
Start = 3 end = 5
binary = 3+5/2 -> 4(index)

Value in index 4 is 10 and its equal to target.

Now output is index 4.

Time complexity -

Best case - O(1) //size does not matter if element is found in first index
Worst Case - logN.

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,2,3,5,6,7,9,10};
        int target = 6;
        int ans =binarySearch(arr,target);
        System.out.println(ans);
    }

    static int binarySearch(int[] arr, int target) {
        int start =0;
        int end = arr.length-1;
        while(start <= end) {
            int mid = start+(end-start)/2;
        if(target < arr[mid]) {
            end = mid-1;
        }else if(target > arr[mid]) {
            start = mid+1;
        }else {
            return mid;
        }
        }
        return -1;
    }
}

Output - 4