What is binary search?

Binary search is one of the searching algorithm used to find element in sorted array in Logarithmic running time complexity

**Note:** Binary search can only be applied in sorted array

**Why binary search is better then linear search**

Binary search has O(log(n)) logarithmic time complexity and linear search has O(n) linear time complexity

**How Binary Search Work**

Binary search use divide and conquer strategy to search element in given array. Binary search divide the searching area into exact half in each pass.

start : it store the value of starting index

end : it stores the value of ending index

mid : it stores the value of middle index

start = 0

end = array_length -1

mid = (start + end)/2 // but that's not good practice

(start + end) can sometime exceed the integer limit

mid = start + (end - start)/2 // this is the correct way

Suppose at first we have an array nums = { 1, 2, 4, 8, 10, 50, 70, 88, 100 } (note here array is sorted) and your target element is 70.

First check if middle element of array is equal to target or not. If it's equal then return middle index or mid. If not then check if target is smaller or bigger then middle element.

If target is smaller then middle element reduce the search space, end = mid -1. Now new search space is (start, mid -1).

If target is bigger the middle element reduce the search space, start = mid +1. Now new search space is (mid+1, end).

Hence, at each pass the search space will reduce into half until start <= end. If start became greater then end, the loop will break

**Algorithm**

Binary search in Java

```
import java.util.Arrays;
public class BinarySearch {
public static void main(String[] args) {
int[] nums = { 1, 2, 3, 19, 29, 40, 60, 100 };
int target = 40;
System.out.println(Arrays.toString(nums));
System.out.println(binarySearch(nums, target));
}
static int binarySearch(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
}
```

## Top comments (0)