Форум dkLab и Denwer
Здесь общаются Web-разработчики.
Генеральный спонсор:
Хостинг «Джино»

бинарный поиск элементов в сортированном массиве (Rumata)
Author Message
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Sun Oct 31, 2004 11:12 pm (написано за 31 секунду)
   Post subject: бинарный поиск элементов в сортированном массиве
Reply with quote

Code (JavaScript): скопировать код в буфер обмена
Array.prototype.search = function(searchItem, compare, right)
{
    if (searchItem === undefined) return null;
    if (!compare) {
        compare = function(a, b)
        {
            return (String(a) == String(b)) ? 0 : (String(a) < String(b)) ? -1 : +1;
        }
    }
    var found = false, l = 0, u = this.length - 1;
    while (l <= u) {
        var m = parseInt((l + u) / 2);
        switch (compare(this[m], searchItem)) {
        case -1:
            var ml = m;
            l = m + 1;
            break;
        case +1:
            var mu = m;
            u = m - 1;
            break;
        default:
            found = true;
            if (right) {
                l = m + 1;
            } else {
                u = m - 1;
            }
        }
    }
    if (!found) {
        this.insertIndex = (ml + 1) || mu || 0;
        //this.insertIndex = (ml) ? ml + 1 : mu;
        return -1;
    }
    return (right) ? u : l;
}

Array.prototype.indexOf = function(searchItem, compare)
{
    return this.search(searchItem, compare, false);
}

Array.prototype.lastIndexOf = function(searchItem, compare)
{
    return this.search(searchItem, compare, true);
}
функции поиска позиции элемента в сортированном массиве - производится поиск элемента и возвращает:
1. индекс найденного элемента
2. значение '-1', если элемент отсутствует. в этом случае создается новое свойство Array.prototype.insertIndex, которое возвращает значение индекса массива, куда можно добавить элемент
3. значение 'null', если параметр 'searchItem' не задан

необязательный параметр 'compare' задает способ сравнения элементов массива и может быть полезен при поиске элемента в массиве, отсортированном в антилексикографическом порядке, или массиве более сложной структуры. по умолчанию, производится поиск элементов в лексикографическом порядке по возрастанию значений элементов, которые рассматриваются как строки (для совместимости с методом Array.prototype.sort).

Array.prototype.search - поиск позиции элемента 'searchItem' в массиве. поиск крайнего левого или крайнего правого элемента определятся необязательным параметром 'right'
Array.prototype.indexOf - поиск левого элемента из группы повторяющихся элементов
Array.prototype.lastIndexOf - поиск правого элемента из группы повторяющихся элементов
во всех методах критерий поиска определяется вторым необязательным параметром 'compare'.

пример использования:
Code (JavaScript): скопировать код в буфер обмена
//
//

//
fwrdCmp = function(a, b) { return (a == b) ? 0 : (a < b) ? -1 : +1; }

//
backCmp = function(a, b) { return (a == b) ? 0 : (a > b) ? -1 : +1; }

//
var x = [9, 1, 2, 5, 4, 9, 3, 4, 4, 1, 3];
//
var y = clone(x).sort(fwrdCmp);
//
var z = clone(x).sort(backCmp);

//
var value = -1;

//
var by1 = y.indexOf(value, fwrdCmp);
var by2 = y.lastIndexOf(value, fwrdCmp);

var bz1 = z.indexOf(value, backCmp);
var bz2 = z.lastIndexOf(value, backCmp);

document.writeln("unsorted array: " + x);
document.writeln("searching value = " + value);

document.writeln("array: [" + y + "]");
if (by1 < 0) {
    document.writeln("insert index: " + y.insertIndex);
} else {
    document.writeln("found indexes: " + [by1, by2]);
}

document.writeln("array: [" + z + "]");
if (bz1 < 0) {
    document.writeln("insert index: " + z.insertIndex);
} else {
    document.writeln("found indexes: " + [bz1, bz2]);
}
результат работы функции
Code (any language): скопировать код в буфер обмена
unsorted array: 9,1,2,5,4,9,3,4,4,1,3
searching value = -1
array: [1,1,2,3,3,4,4,4,5,9,9]
insert index: 0
array: [9,9,5,4,4,4,3,3,2,1,1]
insert index: 11
совместимость:
Mozilla, Firefox, Opera, MSIE, MS JScript

Last edited by Rumata on Wed Nov 03, 2004 10:59 am; edited 2 times in total
Back to top
View user's profile Send private message
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Sun Oct 31, 2004 11:21 pm (спустя 9 минут; написано за 4 секунды)
   Post subject:
Reply with quote

требования к функции 'compare'
Функция должна возвращать одно из трех значений:
Code (JavaScript): скопировать код в буфер обмена
//
// -1: a < b
//  0: a == b
// +1: a > b
function compare(a, b) {
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}
если необходимо искать данные в массиве, отсортированном в обратном порядке, то следует реализовать соответствующую функцию и пердавать вторым параметром
Code (JavaScript): скопировать код в буфер обмена
function compare(a, b) {
  if (a > b) return -1;
  if (a < b) return 1;
  return 0;
}
по умолчанию выполняется сортировка элментов, преобразованных в строки
Code (JavaScript): скопировать код в буфер обмена
function cmp(a, b) {
  if (String(a) < String(b)) return -1;
  if (String(a) > String(b)) return 1;
  return 0;
}
Back to top
View user's profile Send private message
Дмитрий Котеров
Администратор



Joined: 10 Mar 2003
Posts: 13665
Карма: 411
   поощрить/наказать


PostPosted: Mon Nov 01, 2004 12:31 am (спустя 1 час 9 минут; написано за 1 минуту 36 секунд)
   Post subject:
Reply with quote

Небольшое замечание. Была бы очень полезна возможность в случае невозможности найти точное совпаниение возврата последнего элемента, на котором закончился поиск. Эти, например пригодится при реализации "горячего" поиска в combo-списке, при поиске места вставки нового элемента (если нужно сохранить алфавитный порядок) и т.д. Например, сделать четвертый булевский параметр.
Back to top
View user's profile Send private message Send e-mail
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Mon Nov 01, 2004 12:51 am (спустя 20 минут; написано за 1 минуту 31 секунду)
   Post subject:
Reply with quote

Дмитрий Котеров wrote:
Была бы очень полезна возможность в случае невозможности найти точное совпаниение возврата последнего элемента, на котором закончился поиск
ага... как вариант
может имеет смысл, сделать возврат ближайшей позиции, куда можно вставить данный отсутствующий элемент?
Back to top
View user's profile Send private message
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Mon Nov 01, 2004 2:15 am (спустя 1 час 24 минуты; написано за 5 минут 15 секунд)
   Post subject:
Reply with quote

подправил первый пост с учетом пожеланий Дмитрия
Back to top
View user's profile Send private message
WingedFox
Профессионал



Joined: 29 Apr 2003
Posts: 4064
Карма: 269
   поощрить/наказать

Location: Питер

PostPosted: Tue Nov 02, 2004 6:24 pm (спустя 1 день 16 часов 8 минут)
   Post subject:
Reply with quote

В дополнение - советую использовать www.dithered.com/javascript/array/index.html
Расширения
Array.concat()
Array.copy()
Array.pop()
Array.push()
Array.shift()
Array.slice()
Array.splice()
Array.unshift()
Back to top
View user's profile Send private message
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Wed Nov 03, 2004 11:00 am (спустя 16 часов 36 минут; написано за 1 минуту 43 секунды)
   Post subject:
Reply with quote

чуть подправил первый пост. были некорректые обработки пустых массивов типа
Code (JavaScript): скопировать код в буфер обмена
var emptyArr1 = [];
var emptyArr2 = new Array();
теперь обрабатывает корректно и возвращает индекс вставки, равный нулю
Back to top
View user's profile Send private message
Дмитрий Котеров
Администратор



Joined: 10 Mar 2003
Posts: 13665
Карма: 411
   поощрить/наказать


PostPosted: Fri Nov 26, 2004 9:10 pm (спустя 23 дня 10 часов 10 минут; написано за 1 минуту 15 секунд)
   Post subject:
Reply with quote

Все-таки я бы настоятельно порекомендовал переименовать эту функцию в bsearch(), а indexOf и lastIndexOf убрать. Дело в том, что функция специфична: работает только для отсортированных массивов, а не для всех. Те названия, которые есть сейчас, могут ввести в серьезное заблуждение.
Back to top
View user's profile Send private message Send e-mail
Rumata
Профессионал



Joined: 17 Aug 2003
Posts: 1850
Карма: 185
   поощрить/наказать


PostPosted: Thu Dec 02, 2004 1:32 pm (спустя 5 дней 16 часов 22 минуты; написано за 55 секунд)
   Post subject:
Reply with quote

я предлагаю такие имена
Code (JavaScript): скопировать код в буфер обмена
Array.prototype.bsearch()
Array.prototype.bsearchLeft()
Array.prototype.bsearchRight()
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic All times are GMT + 3 Hours
Page 1 of 1    Email to a Friend.
You cannot post new topics in this forum. You cannot reply to topics in this forum. You cannot edit your posts in this forum. You cannot delete your posts in this forum. You cannot vote in polls in this forum. You cannot attach files in this forum. You can download files in this forum.
XML