算法练习_二分查找

Posted on | Edited on | Comments: | Views:
二分查找的学习笔记以及代码实现

概念

问题描述

给定 n 个元素，这些元素是有序的（假定为升序），从中查找特定元素 x 。

算法思想

将有序序列分解为规模大致相等的两部分，然后取中间元素与特定元素进行比较，如果与中间元素相等，则查找成功，算法终止；如果比中间元素小，则在序列的前半部分查找（重复分解并查找的操作）；否则，在序列的后半部分查找（重复分解并查找的操作）。

图解

iKwujg.png

代码实现

Clojure:

1
2
3
4
5
6
7
8
9
10
11
(defn binary-search [items x]
  (let [items' (sort items)]
    (letfn [(binary-search' [items' x]
              (cond (empty? items') -1
                    (= x (first (drop (/ (count items') 2) items'))) 1 
                    :else  (cond (= 1 (count items')) -1
                                 (> x (first (drop (/ (count items') 2) items')))(binary-search' (drop (/ (count items') 2) items') x)
                                 :else (binary-search' (take (/ (count items') 2) items') x))))]
      (binary-search' items' x))))

(println (binary-search '(2 5 8 19 40 3) 9))

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int rank(int[] a, int k) {
        if (a.length == 0) {
            return -1;
        }
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (k == a[mid]) {
                return mid;
            }
            if (k < a[mid]) {
                hi = mid - 1;
            }
            if (k > a[mid]) {
                lo = mid + 1;
            }
        }
        return -1;
    }

参考文档

《趣学算法》