Binary search is a search algorithm that works by repeatedly dividing the search interval in half. It is a very efficient algorithm for searching sorted arrays or lists.
The algorithm begins by comparing the target value with the middle element of the array or list. If the target value matches the middle element, the search is successful and the index of the middle element is returned. If the target value is less than the middle element, the algorithm searches the left half of the array or list. If the target value is greater than the middle element, the algorithm searches the right half of the array or list. This process is repeated until the target value is found or until the search interval is empty.
Binary search has a time complexity of O(log n), where n is the number of elements in the array or list. This means that the time it takes to search for an element in a sorted array or list using binary search increases logarithmically with the size of the array or list. This makes binary search much faster than linear search for large datasets.
fun binarySearch(arr: IntArray, target: Int): Int {
var left = 0
var right = arr.size - 1
while (left <= right) {
val mid = (left + right) / 2
if (arr[mid] == target) {
return mid
} else if (arr[mid] < target) {
left = mid + 1
} else {
right = mid - 1
}
}
return -1 // target not found in the array
}The binarySearch function takes a sorted array of integers arr and a target integer target, and returns the index of the target element in the array if it exists. If the target element is not found, the function returns -1.
The function uses a while loop to repeatedly divide the search interval in half until the target element is found or until the search interval is empty. The left and right variables represent the left and right endpoints of the search interval, and the mid variable represents the midpoint of the search interval. The algorithm compares the target value with the middle element of the array and narrows the search interval to the left or right half depending on the result of the comparison. If the target value is found, the function returns the index of the element containing the target value. If the search interval is empty and the target value is not found, the function returns -1.
The complete is
fun main() {
val arr = intArrayOf(2, 5, 8, 12, 16)
val target = 8
val index = binarySearch(arr, target)
if (index != -1) {
println("Target found at index $index")
}
else {
println("Target not found in the array")
}
}
fun binarySearch(arr: IntArray, target: Int): Int {
var left = 0
var right = arr.size - 1
while (left <= right) {
val mid = (left + right) / 2
if (arr[mid] == target) {
return mid
} else if (arr[mid] < target) {
left = mid + 1
} else {
right = mid - 1
}
}
return -1 // target not found in the array
}