Wyszukiwanie binarne (binary search)

1def binary_search(a, target):2    lo, hi = 0, len(a) - 13    while lo <= hi:4        mid = (lo + hi) // 25        if a[mid] == target:6            return mid7        if a[mid] < target:8            lo = mid + 1  # search the right half9        else:10            hi = mid - 1  # search the left half11    return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9]  # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))

1function binarySearch(a, target) {2    let lo = 0;3    let hi = a.length - 1;4    while (lo <= hi) {5        const mid = Math.floor((lo + hi) / 2);6        if (a[mid] === target) return mid;7        if (a[mid] < target) {8            lo = mid + 1; // search the right half9        } else {10            hi = mid - 1; // search the left half11        }12    }13    return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));

1public class Main {2    static int binarySearch(int[] a, int target) {3        int lo = 0;4        int hi = a.length - 1;5        while (lo <= hi) {6            int mid = (lo + hi) / 2;7            if (a[mid] == target) return mid;8            if (a[mid] < target) {9                lo = mid + 1; // search the right half10            } else {11                hi = mid - 1; // search the left half12            }13        }14        return -1;15    }16
17    public static void main(String[] args) {18        int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19        System.out.println("Index of 5: " + binarySearch(nums, 5));20        System.out.println("Index of 4: " + binarySearch(nums, 4));21    }22}

1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5    int lo = 0;6    int hi = static_cast<int>(a.size()) - 1;7    while (lo <= hi) {8        int mid = lo + (hi - lo) / 2;9        if (a[mid] == target) return mid;10        if (a[mid] < target) {11            lo = mid + 1; // search the right half12        } else {13            hi = mid - 1; // search the left half14        }15    }16    return -1;17}18
19int main() {20    std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21    std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22    std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23    return 0;24}

1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4    int lo = 0;5    int hi = n - 1;6    while (lo <= hi) {7        int mid = lo + (hi - lo) / 2;8        if (a[mid] == target) return mid;9        if (a[mid] < target) {10            lo = mid + 1; /* search the right half */11        } else {12            hi = mid - 1; /* search the left half */13        }14    }15    return -1;16}17
18int main(void) {19    int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20    int n = sizeof(nums) / sizeof(nums[0]);21    printf("Index of 5: %d\n", binary_search(nums, n, 5));22    printf("Index of 4: %d\n", binary_search(nums, n, 4));23    return 0;24}

1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14    DECLARE lo : INTEGER15    DECLARE hi : INTEGER16    DECLARE mid : INTEGER17    lo ← 118    hi ← n19    WHILE lo <= hi DO20        mid ← (lo + hi) DIV 221        IF nums[mid] = target THEN22            RETURN mid23        ENDIF24        IF nums[mid] < target THEN25            // Target is larger, search the right half26            lo ← mid + 127        ELSE28            // Target is smaller, search the left half29            hi ← mid - 130        ENDIF31    ENDWHILE32    RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)