Binary Search In Java

• Locates a target value in a sorted array/list by successively discarding half of the array
• The algorithm repeatedly examines the element at the middle index and uses it to cut the range of indexes of interest in half
• If we examine the middle element and find it’s too small, we will discard all elements between min and mid
• If the middle element is too large, we will discard all elements between mid and max from consideration.
• The elements should be in sorted order to do a Binary Search
• If the array contains multiple elements with the specified value, there is no guarantee which one will be found, The moment the element is encountered, the search stops

Binary Search code in Java

// Returns the index of an occurrence of target in a,
// or a negative number if the target is not found.
// Precondition: elements of a are in sorted order
public static int binarySearch(int[] a, int target) {
int low= 0;
int high= a.length - 1;
while (low<= high) {
int mid = (low+ high) / 2;
if (a[mid] < target) {
low = mid + 1;
} else if (a[mid] > target) {
high= mid - 1;
} else {
return mid;   // target found
}
}
return -(low + 1);    // target not found
}

Let's do a Binary Search

Rules:

1. Initially, LOW=0, HIGH = Array/ List size-1
2. MID= (LOW+HIGH)/2
3. If Element to be searched >MID(Search on Right Half), LOW = MID+1, HIGH remains same as the previous iteration
4. If Element to be searched <MID (Search on Left Half), LOW remains same as the previous iteration, HIGH= MID-1
5. If LOW>HIGH, Stop Search, return -(LOW+1)

Lets Start...

Consider the following integer array, I want to search for the element 27

Consider the following integer array, I want to search for the element -13

Consider the following integer array, I want to search for the element 66

Consider the following integer array, I want to search for the element 39

Note: the return value will be >= 0 if and only if the Search Element is found.

If the element to be searched is not found, then the return value should be

(–(insertion point) -1). The insertion point is defined as the point
at which the key would be inserted into the list:

This is achieved in the algorithm

return -(low + 1);    // target not found 

It's time for practice …

Consider the following array,

What indexes will be examined as the middle element by a binary search for the Searching the value 30

What value will be returned?

Please post your answers in the comments section

Thank you for reading!