Consider an array of N integers and you need to find if a number, x, exist in that array. The easiest way of doing this is to take each element of the array from the first to the last and check if it matches the search value 100. This method is called a linear search and the problem with linear search is that it can be very time consuming, especially for larger arrays. The time complexity for linear search in the worst-case scenario is defined as O(n), where n is the number of elements in the array. The search can be done a lot quicker if the array is sorted. For example, consider a sorted array of six elements
[10, 15, 23, 40, 75, 80]
The target value or the search values is, say 40.
In this case, you do not have to scan from the first element of the array, instead, you can do the following.
Split the array down the middle to two halves. The position of the middle element is calcula
middle postiion = (start index + end index) / 2 middle postiion = (0 + 5) / 2 = 2 (ignore the decimal part)
The middle position is 2 and middle element is 23. Therefore you will have two sub-arrays like below.
First sub-array contains - [ 10, 15, 23] Second sub-array contains - [ 40, 75, 80]
- If the middle element is the target search element then search returns the element position.
- If the target element is less than the middle element then search the first half of the array.
- if the target element is greater than the middle element then search the second half of the array.
Repeat steps 1 to 4 until you find the search element or the sub-array you are searching for contains more than one element.
In case of our example array, the condition on step 4 holds true. So you have to repeat the steps 1 to 4 on the second sub-array
[40, 75, 80]
This method of searching a target value in an array is known as a binary search. It's a type of "divide and conquer" algorithm where you continuously divide the problem into smaller parts and apply the same logic to get to the solution.
This algorithm can be used to find search for an element on both one dimensional and two dimensional arrays.
Binary Search on 2-D Arrays
Here is a Java program to search for a value in a two dimensional array using binary search algorithm.
public class Main {
// Entry point
public static void main(String[] args) {
int[][] my_array = {{1, 6, 7},
{8, 11, 13 },
{18, 25, 31}};
// Value to search
int target = 25;
// Call binarySearch method
if (binarySearch(my_array, target) > 0)
System.out.println("Found");
else
System.out.println("Not found");
}
/**
* Search a 2-D array for a target value.
* @param a : 2-D array.
* @param searchValue : Target value to search.
* @return 1 if found and 0 if not found.
*/
public static int binarySearch(int a[][], int searchValue){
int rows = a.length;
int cols = a[0].length;
int start = 0;
int end = rows * cols - 1;
int mid, midRow, midCol, midVal;
while (start <= end) {
mid = (start + end) / 2;
midRow = mid / cols;
midCol = mid % cols;
midVal = a[midRow][midCol];
if (midVal == searchValue){
// Return 1 if target found
return 1;
} else if (midVal > searchValue) {
end = mid - 1;
} else if (midVal < searchValue){
start = mid + 1;
}
}
// Return 0 if not found
return 0;
}
}
Returning row and column positions
If you want the binary search method to return the row and column positions when the search value is found, you need to make the following changes.
Change the method definition to return an array.
public static int[] binarySearch(int a[][], int searchValue)Declare an array of size 2 and intialize it with the value -1.
int[] result = {-1, -1};If target found, set row and column values and return result.
if (midVal == searchValue){ result[0] = midRow; result[1] = midCol; return result; }Change the second return statement, to return the initial result array with values -1 in case target value not found.
return result;
Inside the
Mainmethod, change thebinarySearchmethod call to accept result array.int[] result = binarySearch(a, target);
Finally, print the row and column.
System.out.println(result[0] + ", "+ result[1]);
You may also add an
if.. elseblock to check row and column equals -1 (Not Found) and print a different message.
Time complexity
The best-case time complexity of binary search algorithm is O(1) when the target search value is the middle of the array. The worst-case is when an search element does not exist and the time complexity is O(log n) where n is the number of elements in the array.
